Eulerianovo číslo - Eulerian number

v kombinatorika, Eulerianovo číslo A(n, m) je počet obměny z čísel 1 až n ve kterém přesně m prvky jsou větší než předchozí prvek (permutace s m "výstupy"). Jsou to koeficienty Euleriánské polynomy:

${displaystyle A_ {n} (t) = součet _ {m = 0} ^ {n} A (n, m) t ^ {m}.}$

Euleriánské polynomy jsou definovány exponenciální generující funkcí

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

Euleriánské polynomy lze vypočítat podle opakování

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

${displaystyle A_ {n} (t) = t (1-t) cdot A_ {n-1} '(t) + A_ {n-1} (t) cdot (1+ (n-1) t), čtyřkolka ngeq 1.}$

Ekvivalentní způsob, jak tuto definici napsat, je indukce Eulerianových polynomů pomocí

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

${displaystyle A_ {n} (t) = součet _ {k = 0} ^ {n-1} {jiné {n} {k}} A_ {k} (t) cdot (t-1) ^ {n-1 -k}, quad ngeq 1.}$

Další notace pro A(n, m) jsou E(n, m) a ${displaystyle scriptstyle leftlangle {n na vrcholu m} ightangle}$.

Dějiny

Ukazuje polynomy v současnosti známé jako Eulerianovy polynomy v Eulerově díle z roku 1755, Institutiones calculi differentialis, část 2, s. 1. 485/6. Koeficienty těchto polynomů jsou známé jako Eulerianova čísla.

V roce 1755 Leonhard Euler zkoumal ve své knize Institutiones calculi differentialis polynomy α₁(X) = 1, α₂(X) = X + 1, α₃(X) = X² + 4X + 1atd. (viz fax). Tyto polynomy jsou posunutou formou toho, co se nyní nazývá Eulerianovy polynomy A_n(X).

Základní vlastnosti

Pro danou hodnotu n > 0, index m v A(n, m) může nabývat hodnot od 0 do n - 1. Pro pevné n existuje jediná permutace, která má 0 výstupů: (n, n − 1, n - 2, ..., 1). K dispozici je také jediná permutace, která má n - 1 výstupy; toto je rostoucí permutace (1, 2, 3, ..., n). Proto A(n, 0) a A(n, n - 1) jsou 1 pro všechny hodnoty n.

Obrácení permutace pomocí m výstupy vytvoří další permutaci, ve které jsou n − m - 1 výstup. Proto A(n, m) = A(n, n − m − 1).

Hodnoty A(n, m) lze vypočítat "ručně" pro malé hodnoty n a m. Například

n	m	Permutace	A(n, m)
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) (3, 1, 2)	A(3,1) = 4
	2	(1, 2, 3)	A(3,2) = 1

Pro větší hodnoty n, A(n, m) lze vypočítat pomocí rekurzivní vzorec

${displaystyle A (n, m) = (n-m) A (n-1, m-1) + (m + 1) A (n-1, m).}$

Například

${displaystyle A (4,1) = (4-1) A (3,0) + (1 + 1) A (3,1) = 3 imes 1 + 2 imes 4 = 11.}$

Hodnoty A(n, m) (sekvence.) A008292 v OEIS ) pro 0 ≤ n ≤ 9 jsou:

m n	0	1	2	3	4	5	6	7	8
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

Výše trojúhelníkové pole se nazývá Eulerův trojúhelník nebo Eulerův trojúhelník, a sdílí některé společné vlastnosti s Pascalův trojúhelník. Součet řádků n je faktoriál n!.

Explicitní vzorec

Explicitní vzorec pro A(n, m) je^[1]

${displaystyle A (n, m) = součet _ {k = 0} ^ {m + 1} (- 1) ^ {k} {jiný {n + 1} {k}} (m + 1-k) ^ { n}.}$

Z tohoto vzorce i z kombinatorické interpretace je patrné, že ${displaystyle A (n, n) = 0}$ pro ${displaystyle n> 0}$, aby ${displaystyle A_ {n} (t)}$ je polynomiální z stupeň ${displaystyle n-1}$ pro ${displaystyle n> 0}$.

Součtové vlastnosti

Z kombinatorické definice je zřejmé, že součet Eulerianových čísel pro pevnou hodnotu n je celkový počet permutací čísel od 1 do n, tak

${displaystyle sum _ {m = 0} ^ {n-1} A (n, m) = n! {ext {for}} ngeq 1.}$

The střídavý součet Eulerianových čísel pro pevnou hodnotu n souvisí s Bernoulliho číslo B_n+1

${displaystyle sum _ {m = 0} ^ {n-1} (- 1) ^ {m} A (n, m) = {frac {2 ^ {n + 1} (2 ^ {n + 1} -1 ) B_ {n + 1}} {n + 1}} {ext {for}} ngeq 1.}$

Další vlastnosti součtu Eulerianových čísel jsou:

${displaystyle sum _ {m = 0} ^ {n-1} (- 1) ^ {m} {frac {A (n, m)} {jiný {n-1} {m}}} = 0 {ext { pro}} ngeq 2,}$

${displaystyle sum _ {m = 0} ^ {n-1} (- 1) ^ {m} {frac {A (n, m)} {jiný {n} {m}}} = (n + 1) B_ {n} {ext {for}} ngeq 2,}$

kde B_n je n^th Bernoulliho číslo.

Totožnosti

Eulerianská čísla jsou zapojena do generující funkce pro posloupnost n^th pravomoci:

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

pro ${displaystyle ngeq 0}$. To předpokládá, že 0⁰ = 0 a A(0,0) = 1 (protože existuje jedna permutace bez prvků a nemá žádné výstupy).

Worpitzkyho identita^[2] vyjadřuje Xⁿ jako lineární kombinace euleriánských čísel s binomické koeficienty:

${displaystyle x ^ {n} = součet _ {m = 0} ^ {n-1} A (n, m) {jiné {x + m} {n}}.}$

Z Worpitzkyho identity to vyplývá

${displaystyle sum _ {k = 1} ^ {N} k ^ {n} = součet _ {m = 0} ^ {n-1} A (n, m) {jiné {N + 1 + m} {n + 1}}.}$

Další zajímavá identita je

${displaystyle {frac {e} {1-ex}} = součet _ {n = 0} ^ {infty} {frac {A_ {n} (x)} {n! (1-x) ^ {n + 1} }}.}$

Čitatel na pravé straně je Eulerianův polynom.

Pro pevnou funkci ${displaystyle f: mathbb {R} ightarrow mathbb {C}}$ který je integrovatelný ${displaystyle (0, n)}$ máme integrální vzorec ^[3]

${displaystyle int _ {0} ^ {1} cdots int _ {0} ^ {1} fleft (leftlfloor x_ {1} + cdots + x_ {n} ightfloor ight) dx_ {1} cdots dx_ {n} = součet _ {k} A (n, k) {frac {f (k)} {n!}}.}$

Euleriánská čísla druhého druhu

Obměny multiset {1, 1, 2, 2, ···, n, n} které mají vlastnost, že pro každého k, všechna čísla, která se objevují mezi dvěma výskyty k v permutaci jsou větší než k jsou počítány podle dvojitý faktoriál číslo 2n-1) !!. Eulerianovo číslo druhého druhu, označené ${displaystyle scriptstyle leftlangle! leftlangle {n na vrcholu m} ightangle! ightangle}$, spočítá počet všech takových permutací, které mají přesně m výstupy. Například pro n = 3 existuje 15 takových permutací, 1 bez výstupů, 8 s jediným výstupem a 6 se dvěma výstupy:

332211,

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

112233, 122133, 112332, 123321, 133122, 122331.

Euleriánská čísla druhého druhu uspokojují relaci opakování, která vyplývá přímo z výše uvedené definice:

${displaystyle leftlangle !! leftlangle {n atop m} ightangle !! ightangle = (2n-m-1) leftlangle !! leftlangle {n-1 attop m-1} ightangle !! ightangle + (m + 1) leftlangle !! leftlangle {n-1 na vrcholu m} ightangle !! ightangle,}$

s počáteční podmínkou pro n = 0, vyjádřeno v Iverson držák notace:

${displaystyle leftlangle !! leftlangle {0 atop m} ightangle !! ightangle = [m = 0].}$

Odpovídajícím způsobem je zde označen eulerovský polynom druhého druhu P_n (neexistuje pro ně žádná standardní notace) jsou

${displaystyle P_ {n} (x): = součet _ {m = 0} ^ {n} leftlangle !! leftlangle {n na vrcholu m} ightangle !! ightangle x ^ {m}}$

a výše uvedené relace opakování jsou přeloženy do relace opakování pro sekvenci P_n(X):

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

s počátečním stavem

${displaystyle P_ {0} (x) = 1.}$

Druhá recidiva může být napsána v nějak kompaktnější formě pomocí integračního faktoru:

${displaystyle (x-1) ^ {- 2n-2} P_ {n + 1} (x) = left (x (1-x) ^ {- 2n-1} P_ {n} (x) ight) ^ { primární }}$

takže racionální funkce

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

uspokojuje jednoduché autonomní opakování:

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

odkud člověk získá Eulerianovy polynomy jako P_n(X) = (1−X)²ⁿ u_n(X) a Eulerianova čísla druhého druhu jako jejich koeficienty.

Zde jsou některé hodnoty euleriánských čísel druhého řádu (sekvence A008517 v OEIS ):

m n	0	1	2	3	4	5	6	7	8
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

Součet n-tý řádek, což je také hodnota P_n(1), je (2n − 1)!!.

Reference

• Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Základy diferenciálního počtu, s aplikacemi pro konečnou analýzu a řady]. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
• Carlitz, L. (1959). "Euleriánská čísla a polynomy". Matematika. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR  3029225.
• Gould, H. W. (1978). „Vyhodnocení součtu konvolučních sil pomocí Stirlingova a Eulerianova čísla“. Fib. Kvart. 16 (6): 488–497.
• Desarmenien, Jacques; Foata, Dominique (1992). "Podepsaná Eulerianova čísla". Diskrétní matematika. 99 (1–3): 49–58. doi:10.1016 / 0012-365X (92) 90364-L.
• Lesieur, Leonce; Nicolas, Jean-Louis (1992). "Na Euleriánských číslech 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). „Euleriánská čísla s parametry zlomkové objednávky“. Aequationes Mathematicae. 46 (1–2): 119–142. doi:10.1007 / bf01834003. S2CID  121868847.
• Koutras, M.V. (1994). „Euleriánská čísla spojená se sekvencemi polynomů“. Fib. Kvart. 32 (1): 44.
• Graham; Knuth; Patashnik (1994). Konkrétní matematika: Nadace pro informatiku (2. vyd.). Addison-Wesley. 267–272.
• Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). "O určitých problémech se sčítáním a zobecnění Eulerianových polynomů a čísel". Diskrétní matematika. 204 (1–3): 237–247. doi:10.1016 / S0012-365X (98) 00379-3.
• Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulliho funkce, derivační polynomy a Eulerianovy polynomy". arXiv:0710.1124 [matematika ].
• Petersen, T. Kyle (2015). "Eulerianská čísla". Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. s. 3–18. doi:10.1007/978-1-4939-3091-3_1. ISBN  978-1-4939-3090-6. Chybějící nebo prázdný | název = (Pomoc)

Citace

externí odkazy

• Euleriánské polynomy na OEIS Wiki.
• „Eulerian Numbers“. MathPages.com.
• Weisstein, Eric W. „Eulerianovo číslo“. MathWorld.
• Weisstein, Eric W. „Eulerův číselný trojúhelník“. MathWorld.
• Weisstein, Eric W. „Worpitzkyho identita“. MathWorld.
• Weisstein, Eric W. „Euleriánský trojúhelník druhého řádu“. MathWorld.
• Eulerova matice (zobecněné indexy řádků, divergentní součet)