Fubini-szám

A matematikában, közelebbről a kombinatorika , a Fubini számokat vagy megrendelhető Bell számok felsorolni a megrendelt partíciók egy sor E és n elemek, vagyis a véges családok nemüres diszjunkt rész E akinek találkozó egyenlő E . Például n = 3 esetén 13 rendezett partíció van : 6 típusú , 3 típusú , 3 típusú , plusz . $\{ABC\}$ ${\ displaystyle \ left (\ {a \}, \ {b \}, \ {c \} \ right)}$ ${\ displaystyle \ left (\ {a \}, \ {b, c \} \ right)}$ ${\ displaystyle \ left (\ {a, b \}, \ {c \} \ right)}$ ${\ displaystyle \ bal (\ {a, b, c \} \ jobb)}$

Bemutatás

Ezzel egyenértékűen a Fubini-számok megszámolják n objektum rangsorolását , esetleg kapcsolatokkal, mint a lóverseny eredményeiben . Ezért hívják őket a lovak számozására is . Például n = 3, 13 lehetséges exæquos rangsor vannak osztva hat osztályozási nélkül exæquos például , 3 két első exæquos mint , 3, két második exæquos, mint , és egy három exæquos, . $a <b <c$ ${\ displaystyle a <b \ equiv c}$ ${\ displaystyle a \ equiv b <c}$ ${\ displaystyle a \ equiv b \ equiv c}$

A név „Fubini számok” származik bevezetésük Louis Comtet formájában a felsorolás a különböző aequivalens összeget vagy egy n -szeres szerves , ennek következtében a Fubini tétel . Például egy kettős integrálnak három egyenértékű alakja van:

{\ displaystyle \ int _ {A} \ left (\ int _ {B} f (x, y) \, {\ text {d}} y \ right) \, {\ text {d}} x = \ int _ {B} \ balra (\ int _ {A} f (x, y) \, {\ text {d}} x \ jobbra) \, {\ text {d}} y = \ int _ {A \ alkalommal B} f (x, y) \, {\ text {d}} (x, y)}

A "rendezett harangszámok" név a rendezetlen partíciókat számláló harangszámokból származik .

A Fubini-számok alkotják az OEIS A000670 szekvenciáját :

{\ displaystyle F_ {0} = 1, \ quad F_ {1} = 1, \ quad F_ {2} = 3, \ quad F_ {3} = 13, \ quad F_ {4} = 75, \ quad F_ { 5} = 541, \ quad F_ {6} = 4683, \ quad \ ldots}

a jelölés összetéveszthető a Fibonacci-számok , valamint a Fermat azonos jelölésével . $F_ {n}$

A Fubini-számok kiszámolhatók binomiális együtthatókat tartalmazó összegző képlettel vagy megismétlődési relációval . A rendezett partíciók mellett számos más típusú kombinatorikus objektumot is felsorolnak, például egy egész négyzet rendezett multiplikatív partícióit vagy a permutohedron összes dimenziójának arcát (például a hatszög összes dimenziójának arca 1 + 6 + 6 = 13, a csonka oktaéderé pedig 1 + 14 + 36 + 24 = 75).

Fubini-számok és Cayley-fák

A Fubini-számok Cayley (1859) cikkében jelennek meg; az utóbbi kapott őket, mint a száma bizonyos fák n + 1 levelek, fák, amelyeknek utak a gyökérből egy levél van az azonos hosszúságú, és amelynek a csomópontok száma a távolságot i a gyökér szigorúan kisebb, mint a csomópontok száma az i + 1 távolságban . Egy ilyen fában n szomszédos levélpár van, amelyekhez a legkisebb közös őseik magasságát tulajdonítjuk ; ezek az utolsó számok meghatározzák a ranglista rangsorát ezen levelpárok holtversenyével, és fordítva ez a rangsor határozza meg a fát.

Képletek

Kifejezés a második fajta Stirling-számok függvényében

Ezek a számok számítanak a válaszfalak egy n- set in k alkatrészeket, és ezek k részei permutálhatjuk által $k$ $!$ módon: ${\ displaystyle S (n, k)}$

{\ displaystyle F_ {n} = \ sum _ {k = 0} ^ {n} k! S (n, k)}

Az explicit Stirling-szám képlet felhasználásával a következő zárt képletet vonjuk le binomiális együtthatókkal :

${\ displaystyle F_ {n} = \ sum _ {k = 0} ^ {n} \ sum _ {i = 0} ^ {k} (- 1) ^ {ki} {\ binom {k} {i}} i ^ {n}}$

Kifejezés az euleri számok függvényében

Ezek az $A$ $($ $n, k$ $)$ számok n objektum permutációit számlálva k "emelkedéssel" (vagy k "ereszkedéssel"):

{\ displaystyle F_ {n} = \ sum _ {k = 0} ^ {n} 2 ^ {k} A (n, k) = A_ {n} (2),}

hol van az n index euleri polinomja . Az alábbi demonstráció a. $Év}$

Vegye figyelembe az összes permutációt , az emelkedőket "<" -nel, az ereszkedéseket pedig ">" -gal jelölve. Átalakítsuk a permutáció ">" jeleit "<" vagy " " (így bizonyos szempontból). Így tetszőleges rangsort kapunk exæquókkal. Például generál és . ${\ displaystyle [n]}$ $k$ $\ egyenértékű$ $2 ^ {k}$ ${\ displaystyle 1 <3> 2}$ ${\ displaystyle 1 <3 <2}$ ${\ displaystyle 1 <3 \ equiv 2}$

Ezért megkapjuk, és megnövelhetjük az összeget n karakterig . ${\ displaystyle F_ {n} = \ sum _ {k = 0} ^ {n-1} 2 ^ {k} A (n, k)}$ ${\ displaystyle A (n, n) = 0}$

Ismétlődés relációja

A Fubini-számok a kiindulástól kezdve az erős ismétlődési relációval számíthatók : ${\ displaystyle F_ {0} = 1}$

{\ displaystyle F_ {n} = \ sum _ {k = 1} ^ {n} {\ binom {n} {k}} F_ {nk} = \ sum _ {k = 0} ^ {n-1} { \ binom {n} {k}} F_ {k}}

Ez a képlet abból a tényből származik, hogy egy n -halmaz rendezett partícióját úgy kapjuk meg, hogy egy nem üres halmazt választunk $k$ elemekkel (a partíció első osztálya), majd egy rendezett partícióval a többi $nk$ elemre.

Exponenciális generátor funkció

A Fubini-számok exponenciális generátorfüggvényét a

{\ displaystyle f (z) = \ sum _ {n = 0} ^ {\ infty} F_ {n} {\ frac {z ^ {n}} {n!}} = {\ frac {1} {2- e ^ {z}}}.}

Demonstráció

Termék szerint Cauchy . ${\ displaystyle e ^ {z} f (z) = \ sum _ {n = 0} ^ {+ \ infty} \ bal (\ sum _ {k = 0} ^ {n} {\ frac {F_ {k} } {k! (nk)!}} \ jobbra) z ^ {n} = 1 + \ sum _ {n = 1} ^ {+ \ infty} \ balra ({\ frac {1} {n!}} \ összeg _ {k = 0} ^ {n-1} {\ binom {n} {k}} F_ {k} + {\ frac {F_ {n}} {n}} \ jobbra) z ^ {n}}$

Az ismétlődési relációt felhasználva megkapjuk , tehát az eredményt. ${\ displaystyle e ^ {z} f (z) = 1 + \ sum _ {n = 1} ^ {+ \ infty} {\ frac {2F_ {n}} {n!}} z ^ {n} = 2f (z) -1}$

Ennek megírásával és kibővítésével megkapjuk a Fubini-számok kifejezését sorozat összegeként : ${\ displaystyle {\ frac {1} {2-e ^ {z}}} = \ sum _ {k \ geqslant 0} {\ frac {e ^ {kz}} {2 ^ {k + 1}}}}$ ${\ displaystyle e ^ {kz}}$

{\ displaystyle F_ {n} = {\ frac {1} {2}} \ sum _ {k = 0} ^ {+ \ infty} {\ frac {k ^ {n}} {2 ^ {k}}} ,}

expresszió kell összehasonlítani a Dobinski-képlet a Bell számok .

Arra is következtetünk, hogy a Fubini-számok a végtelen mátrix első sorának számai , ahol $I$ az identitásmátrix , $T pedig$ a felső háromszög alakú Pascal-mátrix . ${\ displaystyle (2I-T) ^ {- 1}}$

Egyenértékű

Egy görbe integrál a és alkalmazza a reziduumtétel a Fubini számok fejezték ki a végtelen összeg ${\ displaystyle {\ frac {f (z)} {z ^ {n + 1}}}}$ ${\ displaystyle n \ geqslant 1}$

{\ displaystyle F_ {n} = {\ frac {n!} {2}} \ sum _ {k = - \ infty} ^ {\ infty} {\ frac {1} {(\ ln 2 + 2ik \ pi) ^ {n + 1}}}}

amelyből levezetjük az egyenértéket

{\ displaystyle F_ {n} \ sim {\ frac {n!} {2 (\ ln 2) ^ {n + 1}}}.}

Mivel az ln 2 kisebb, mint 1, ez azt mutatja, hogy a Fubini-számok exponenciális tényezővel haladják meg a faktoriálokat (amelyek egyenlőtlen rangokat számítanak). Következtethetünk

{\ displaystyle {\ frac {F_ {n + 1}} {F_ {n}}} \ sim n \ ln 2.}

Moduláris megismétlődés és periodicitások

Az ismétlődési reláció segítségével megmutatjuk, hogy ezek a számok engedelmeskednek a moduláris aritmetika bizonyos periodikus modelljeinek : n elég nagy esetén

{\ displaystyle F_ {n + 4} \ equiv F_ {n} {\ pmod {10}},}

{\ displaystyle F_ {n + 20} \ equiv F_ {n} {\ pmod {100}},}

{\ displaystyle F_ {n + 100} \ equiv F_ {n} {\ pmod {1000}},}

és

{\ displaystyle F_ {n + 500} \ equiv F_ {n} {\ pmod {10000}}.}

Számos más moduláris azonosságot adott meg Good (1975).

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia " Rendelt harangszám " című cikkéből származik ( lásd a szerzők felsorolását ) .

Jean-Marie DE KONINCK, ezek a számok, amelyek elbűvölnek minket , Párizs, Ellipszis,2008( ISBN 978-2-7298-3851-5 ) , p. 4
Ezek a lehetséges kapcsolatokkal rendelkező osztályozások reflexív és transzitív bináris relációkká formálhatók, ahol bármely pár összehasonlítható, más szóval teljes előrendelés .
Louis Comtet, Kombinatorikus elemzés, kötet második , PUF,1970, P. 64.
1, 14, 36, 24 az OEIS A019538 után a negyedik sor .
(a) Arthur Cayley, " az analitikai formái úgynevezett Lejárt fák, használt " , Philosophical Magazine, Series IV, 18 (121) A Összegyűjtött művei Arthur Cayley, p. 112 ,1859, P. 374–378 ( online olvasás )
R. L. Graham, DE Knuth, O. Patashnik, Beton matematika, 7.44. Gyakorlat , International Thomson Publishing France, 1998 p. ( ISBN 2-84180-981-1 ) , p. 401 és 604
RL Graham, DE Knuth, O. Patashnik, Concretes Mathematics, 7.44. Gyakorlat , International Thomson Publishing France, 1998 p. ( ISBN 2-84180-981-1 ) , p. 401 és 604
(in) Barry Lewis, " újragondolása Pascal mátrix " , American Mathematical Monthly, 117 (1) ,2010, P. 50–66. ( online olvasás )
(in) Jó, I. J, " A jelöltek sorrendjeinek száma n, ha a kapcsolatok megengedettek " , Fibonacci Quarterly, 13 ,1975, P. 11–18 ( online olvasás )