यूलेरियन संख्या

Not to be confused with यूलर संख्या or यूलर की संख्या.

कॉम्बिनेटरिक्स में, यूलेरियन संख्या ${\textstyle A(n,k)}$ 1 से ${\textstyle n}$ तक की संख्याओं के क्रमपरिवर्तन की संख्या है जिसमें पूर्णतः ${\textstyle k}$ अवयव पिछले अवयव से बड़े होते हैं (${\textstyle k}$ "आरोही" के साथ क्रमपरिवर्तन)।

लियोनहार्ड यूलर ने अपनी 1755 की पुस्तक कैलकुली डिफरेंशियलिस संस्थाएँ में उनकी और संबंधित बहुपदों की जांच की थी।

1755 से यूलर के कार्य में बहुपदों को वर्तमान में यूलरियन बहुपद के रूप में जाना जाता है, इंस्टीट्यूशन्स कैलकुली डिफरेंशियल, भाग 2, पृष्ठ। 485/6. इन बहुपदों के गुणांकों को यूलेरियन संख्याएँ कहा जाता है।

${\textstyle A(n,k)}$ के लिए अन्य संकेतन ${\textstyle E(n,k)}$ और $\textstyle \left\langle {n \atop k}\right\rangle$ हैं

परिभाषा

यूलेरियन बहुपदों को घातीय जनरेटिंग फलन द्वारा परिभाषित किया गया है

$\sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-e^{(t-1)\,x}}}.$

यूलेरियन संख्याओं को यूलेरियन बहुपदों के गुणांक के रूप में परिभाषित किया जा सकता है:

$A_{n}(t)=\sum _{k=0}^{n}A(n,k)\,t^{k}.$

${\textstyle A(n,k)}$ के लिए स्पष्ट सूत्र है

$A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.$

मूलभूत गुण

• निश्चित ${\textstyle n}$ के लिए एक एकल क्रमचय है जिसमें 0 आरोही हैं: ${\textstyle (n,n-1,n-2,\ldots ,1)}$ वास्तव में, सभी के लिए ${\tbinom {n}{0}}=1$ के रूप में। इसमें औपचारिक रूप से संख्याओं का रिक्त संग्रह, ${\textstyle A(n,0)=1}$ सम्मिलित है। इसलिए ${\textstyle A_{0}(t)=A_{1}(t)=1}$
• ${\textstyle k=1}$ के लिए स्पष्ट सूत्र का तात्पर्य ${\textstyle A(n,1)=2^{n}-(n+1)}$ है, $n$ में एक अनुक्रम जो ${\textstyle 0,0,1,4,11,26,57,\dots }$ पढ़ता है
• ${\textstyle k}$ आरोही के साथ एक क्रमपरिवर्तन को पूरी तरह उलटने से एक और क्रमपरिवर्तन बनता है जिसमें ${\textstyle n-k-1}$ आरोही होते हैं। इसलिए ${\textstyle A(n,k)=A(n,n-k-1)}$ तो एक एकल क्रमपरिवर्तन भी है जिसमें ${\textstyle n-1}$ आरोही है, अर्थात् आरोही क्रमपरिवर्तन ${\textstyle (1,2,\ldots ,n)}$ अतः ${\textstyle A(n,n-1)}$ भी $1$ के समान है
• एक लविश ऊपरी सीमा ${\textstyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k}}$ है। अभी चर्चा की गई सीमाओं के बीच, मान $1$ से अधिक है
• ${\textstyle k\geq n>0}$ के लिए, मान औपचारिक रूप से शून्य हैं, जिसका अर्थ है कि ${\textstyle k}$ के ऊपर कई रकम केवल ${\textstyle n-1}$ तक के ऊपरी सूचकांक के साथ लिखी जा सकती हैं। इसका यह भी अर्थ है कि बहुपद $A_{n}(t)$ वास्तव में ${\textstyle n-1}$ के लिए डिग्री ${\textstyle n>0}$ हैं

त्रिकोणीय सरणी में संख्याओं के सारणीकरण को यूलर त्रिकोण या यूलर का त्रिकोण कहा जाता है। यह पास्कल के त्रिकोण के साथ कुछ सामान्य विशेषताएं साझा करता है। ${\textstyle A(n,k)}$ (sequence A008292 in the OEIS) के लिए ${\textstyle 0\leq n\leq 9}$ हैं:

k n	0	1	2	3	4	5	6	7	8
0	1
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1
6	1	57	302	302	57	1
7	1	120	1191	2416	1191	120	1
8	1	247	4293	15619	15619	4293	247	1
9	1	502	14608	88234	156190	88234	14608	502	1

गणना

${\textstyle n}$, ${\textstyle A(n,k)}$ के बड़े मानों की गणना पुनरावर्ती सूत्र का उपयोग करके भी की जा सकती है

$A(n,k)=(n-k)\,A(n-1,k-1)+(k+1)\,A(n-1,k).$

इस सूत्र को संयोजक परिभाषा से प्रेरित किया जा सकता है और इस प्रकार यह सिद्धांत के लिए प्राकृतिक प्रारंभिक बिंदु के रूप में कार्य करता है।

${\textstyle n}$ और ${\textstyle k}$, के छोटे मानों के लिए, ${\textstyle A(n,k)}$ के मानों की गणना हाथ से की जा सकती है। उदाहरण के लिए

n	k	क्रमपरिवर्तन	A(n, k)
1	0	(1)	A(1,0) = 1
2	0	(2, 1)	A(2,0) = 1
	1	(1, 2)	A(2,1) = 1
3	0	(3, 2, 1)	A(3,0) = 1
	1	(1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 1, 2)	A(3,1) = 4
	2	(1, 2, 3)	A(3,2) = 1

पुनरावृत्ति को उदाहरण पर प्रयुक्त करने पर, हम पा सकते हैं

$A(4,1)=(4-1)\,A(3,0)+(1+1)\,A(3,1)=3\cdot 1+2\cdot 4=11.$

इसी प्रकार, यूलेरियन बहुपद की गणना पुनरावृत्ति द्वारा की जा सकती है

$A_{0}(t)=1,$

$A_{n}(t)=A_{n-1}'(t)\cdot t\,(1-t)+A_{n-1}(t)\cdot (1+(n-1)\,t),{\text{ for }}n>1.$

दूसरे सूत्र को धनात्मक रूप में परिवर्तित किया जा सकता है,

$A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}A_{k}(t)\cdot (t-1)^{n-1-k},{\text{ for }}n>1.$

निम्नलिखित पायथन कार्यान्वयन है।

import math  # python 3.8                                                                                           
                                                                                                                      
def Ank(n, k) -> int:                                                                                             
    """
    Compute A(n, k) using the explicit formula.                                                                             
    """                                                                                                               
    def summand(i):                                                                                                          
        return (-1) ** i * math.comb(n + 1, i) * (k + 1 - i) ** n                                                        
    return sum(map(summand, range(k + 1)))                                                                           

def Anks(n) -> list:                                                                                                    
    """
    Coefficient list for the n'th polynomial A_n(t).                                                                      
    """                                                                                                                   
    return [1] if n == 0 else [Ank(n, k) for k in range(n)]                                                                  

def eval_polynomial(coeffs, t):                                                                                             
    """                                                                                                             
    Polynomial evaluation function.                                                                                   
    """                                                                                                             
    return sum(c * t ** k for k, c in enumerate(coeffs))                                                                      
                                                                                                                      
def An(n, t: float) -> float:                                                                                            
    """
    Polynomial A_n(t).                                                                                                       
    """                                                                                                                       
    return eval_polynomial(Anks(n), t)                                                                                

# Print the first few polynomials                                                                                         
sup = lambda n: str(n).translate(str.maketrans("0123456789", "⁰¹²³⁴⁵⁶⁷⁸⁹"))                                                 
sub = lambda n: str(n).translate(str.maketrans("0123456789", "₀₁₂₃₄₅₆₇₈₉"))                                                  

NUM = 8                                                                                                              
for n in range(NUM):                                                                                                   
    print(f"A{sub(n)}(t) = " + " + ".join(f"{ank} t{sup(k)}" for k, ank in enumerate(Anks(n))))                             
    # E.g. A₇(t) = 1 t⁰ + 120 t¹ + 1191 t² + 2416 t³ + 1191 t⁴ + 120 t⁵ + 1 t⁶                                            

    # Sanity checks                                                                                                            
    assert Ank(n, 1) == 2 ** n - (n + 1)                                                                                
    assert n == 0 or An(n, 1) == math.factorial(n)  # Cardinality check                                                     
    alternating_sum: float = sum((-1)**k * Ank(n, k) / math.comb(n - 1, k) for k in range(n))                             
    assert n < 2 or abs(alternating_sum) < 1e-13

पहचान

किसी परिमित समुच्चय को सीमित रूप से कई छोटे समुच्चयों में विभाजित करने वाली किसी भी संपत्ति के लिए, छोटे समुच्चयों की कार्डिनैलिटी का योग बड़े समुच्चय की कार्डिनैलिटी के समान होता है। यूलेरियन संख्याएँ क्रमपरिवर्तन $n$ अवयव को विभाजित करती हैं , इसलिए उनका योग भाज्य $n!$ के समान होता है . अर्थात।

$\sum _{k=0}^{n-1}A(n,k)=n!,{\text{ for }}n>0.$

साथ ही $A(0,0)=0!$. रिक्त योग परिपाटी के साथ कोलिसन से बचने के लिए, केवल प्रमेयों $n>0$ को बताना सुविधाजनक है केवल।

बहुत अधिक सामान्यतः, एक निश्चित फलन के लिए $f\colon \mathbb {R} \rightarrow \mathbb {C}$ अंतराल पर पूर्णांक $(0,n)$

$\sum _{k=0}^{n-1}A(n,k)\,f(k)=n!\int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right){\mathrm {d} }x_{1}\cdots {\mathrm {d} }x_{n}$

वर्पिट्ज़की की पहचान ${\textstyle x^{n}}$ को द्विपद गुणांक के साथ यूलेरियन संख्याओं के रैखिक संयोजन के रूप में व्यक्त करती है:

$\sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}=x^{n}.$

इससे यह निष्कर्ष निकलता है

$\sum _{k=1}^{m}k^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {m+k+1}{n+1}}.$

प्रत्यावर्ती योगों वाले सूत्र

${\textstyle n}$ के एक निश्चित मान के लिए यूलेरियन संख्याओं का वैकल्पिक योग बर्नौली संख्या ${\textstyle B_{n+1}}$ से संबंधित है

$\sum _{k=0}^{n-1}(-1)^{k}A(n,k)=2^{n+1}(2^{n+1}-1){\frac {B_{n+1}}{n+1}},{\text{ for }}n>0.$

आगे,

$\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,{\text{ for }}n>1$

और

$\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},{\text{ for }}n>1$

बहुपदों से जुड़े सूत्र

समरूपता गुण का तात्पर्य है:

$A_{n}(t)=t^{n-1}A_{n}(t^{-1})$

यूलेरियन संख्याएँ n के अनुक्रम के लिए जनरेटिंग फलन में सम्मिलित हैं

$\sum _{i=1}^{\infty }i^{n}x^{i}={\frac {1}{(1-x)^{n+1}}}\sum _{k=0}^{n}A(n,k)\,x^{k+1}={\frac {x}{(1-x)^{n+1}}}A_{n}(x)$

यह भी मानता है कि,

${\frac {e}{1-e\,x}}=\sum _{n=0}^{\infty }{\frac {1}{n!(1-x)^{n+1}}}A_{n}(x).$

दूसरे क्रम की यूलेरियन संख्याएँ

मल्टीसेट का क्रमपरिवर्तन ${\textstyle \{1,1,2,2,\ldots ,n,n\}}$ है जिसमें यह गुण है कि प्रत्येक k के लिए, क्रमपरिवर्तन में k की दो घटनाओं के बीच दिखाई देने वाली सभी संख्याएँ k से अधिक होती हैं, जिन्हें दोहरे भाज्य संख्या ${\textstyle (2n-1)!!}$ द्वारा गिना जाता है .

दूसरे क्रम की यूलेरियन संख्या, निरूपित $\scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle$, ऐसे सभी क्रमपरिवर्तनों की संख्या की गणना करता है जिनका पूर्णतः m आरोही है। उदाहरण के लिए, n = 3 के लिए 15 ऐसे क्रमपरिवर्तन हैं, 1 बिना आरोही के, 8 एकल आरोही के साथ, और 6 दो आरोही के साथ है:

332211,

221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,

112233, 122133, 112332, 123321, 133122, 122331।

दूसरे क्रम की यूलेरियन संख्याएँ पुनरावृत्ति संबंध को संतुष्ट करती हैं, जो उपरोक्त परिभाषा से सीधे अनुसरण करती है:

$\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-k-1)\left\langle \!\!\left\langle {n-1 \atop k-1}\right\rangle \!\!\right\rangle +(k+1)\left\langle \!\!\left\langle {n-1 \atop k}\right\rangle \!\!\right\rangle ,$

n = 0 के लिए प्रारंभिक नियम के साथ, इवरसन ब्रैकेट नोटेशन में व्यक्त किया गया है:

$\left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =[k=0].$

तदनुसार, दूसरे क्रम का यूलेरियन बहुपद, यहाँ P_n को दर्शाता है (उनके लिए कोई मानक संकेतन उपस्थित नहीं है) हैं

$P_{n}(x):=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle x^{k}$

और उपरोक्त पुनरावृत्ति संबंधों को अनुक्रम p_n(x) के लिए पुनरावृत्ति संबंध में अनुवादित किया गया है:

$P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)$

प्रारंभिक नियम के साथ $P_{0}(x)=1.$. बाद की पुनरावृत्ति को एकीकृत कारक के माध्यम से कुछ हद तक अधिक संक्षिप्त रूप में लिखा जा सकता है:

$(x-1)^{-2n-2}P_{n+1}(x)=\left(x\,(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }$

जिससे तर्कसंगत कार्य हो सकता है

$u_{n}(x):=(x-1)^{-2n}P_{n}(x)$

एक साधारण स्वायत्त पुनरावृत्ति को संतुष्ट करता है:

$u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1$

जहां से कोई दूसरे क्रम के यूलेरियन बहुपद को ${\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)}$ के रूप में प्राप्त करता है, और दूसरे क्रम के यूलेरियन संख्या को उनके गुणांक के रूप में प्राप्त करता है।

निम्न तालिका पहले कुछ दूसरे क्रम के यूलेरियन संख्याओं को प्रदर्शित करती है:

k n	0	1	2	3	4	5	6	7	8
0	1
1	1
2	1	2
3	1	8	6
4	1	22	58	24
5	1	52	328	444	120
6	1	114	1452	4400	3708	720
7	1	240	5610	32120	58140	33984	5040
8	1	494	19950	195800	644020	785304	341136	40320
9	1	1004	67260	1062500	5765500	12440064	11026296	3733920	362880

n-वीं पंक्ति का योग, जो कि मान ${\textstyle P_{n}(1)}$ भी है, ${\textstyle (2n-1)!!}$ है

दूसरे क्रम के यूलेरियन संख्याओं का अनुक्रमण तीन फ्लावर में आता है:

• (sequence A008517 in the OEIS) रिओर्डन और कॉमटेट का अनुसरण करते हुए,
• (sequence A201637 in the OEIS) ग्राहम, नुथ और पाटश्निक का अनुसरण करते हुए,
• (sequence A340556 in the OEIS), गेसल और स्टेनली की परिभाषा का विस्तार।

संदर्भ

• Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Foundations of differential calculus, with applications to finite analysis and series]. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
• Carlitz, L. (1959). "Eulerian Numbers and polynomials". Math. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR 3029225.
• Gould, H. W. (1978). "Evaluation of sums of convolved powers using Stirling and Eulerian Numbers". Fib. Quart. 16 (6): 488–497.
• Desarmenien, Jacques; Foata, Dominique (1992). "The signed Eulerian numbers". Discrete Math. 99 (1–3): 49–58. doi:10.1016/0012-365X(92)90364-L.
• Lesieur, Leonce; Nicolas, Jean-Louis (1992). "On the Eulerian Numbers M=max (A(n,k))". Europ. J. Combinat. 13 (5): 379–399. doi:10.1016/S0195-6698(05)80018-6.
• Butzer, P. L.; Hauss, M. (1993). "Eulerian numbers with fractional order parameters". Aequationes Mathematicae. 46 (1–2): 119–142. doi:10.1007/bf01834003. S2CID 121868847.
• Koutras, M.V. (1994). "Eulerian numbers associated with sequences of polynomials". Fib. Quart. 32 (1): 44.
• Graham; Knuth; Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. pp. 267–272.
• Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). "On certain summation problems and generalizations of Eulerian polynomials and numbers". Discrete Math. 204 (1–3): 237–247. doi:10.1016/S0012-365X(98)00379-3.
• Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials". arXiv:0710.1124 [math.CA].
• Petersen, T. Kyle (2015). Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. pp. 3–18. doi:10.1007/978-1-4939-3091-3_1. ISBN 978-1-4939-3090-6.

बाहरी संबंध

• Eulerian Polynomials at OEIS Wiki.
• "Eulerian Numbers". MathPages.com.
• Weisstein, Eric W. "Eulerian Number". MathWorld.
• Weisstein, Eric W. "Euler's Number Triangle". MathWorld.
• Weisstein, Eric W. "Worpitzky's Identity". MathWorld.
• Weisstein, Eric W. "Second-Order Eulerian Triangle". MathWorld.
• Euler-matrix (generalized rowindexes, divergent summation)