Harangszám

A matematikában az n- edik harangszám ( Eric Temple Bellről kapta a nevét ) egy halmaz partícióinak száma, amelyek n különálló elemet tartalmaznak, vagy ami azonos, akkor az ekvivalencia relációk számát egy ilyen halmazon.

Az első tulajdonságok

Ezek a számok alkotják az OEIS- ből származó A000110 egész sorozatot , amelynek első tagjai kézzel számíthatók: $B_ {0} = 1, \ quad B_ {1} = 1, \ quad B_ {2} = 2, \ quad B_ {3} = 5, \ quad B_ {4} = 15, \ quad B_ {5} = 52, \ quad B_ {6} = 203, \ quad B_ {7} = 877, \ quad \ ldots$ Az első 1-et ér, mert az üres halmaznak pontosan egy partíciója van : az üres partíció, amely nem tartalmaz részeket. Valójában elemei (mivel nincsenek) valóban nem üresek, és ketté-ketté szétválnak, és üres az unió.
A partíciók vannak , és a három partíció a típus . ${\ displaystyle B_ {3} = 5}$ $\{ABC\}$ ${\ displaystyle \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ displaystyle \ {\ {a, b, c \} \}}$ ${\ displaystyle \ {\ {a \}, \ {b, c \} \}}$
A Bell-számokat lépésről lépésre is ki lehet számítani a következő ismétlődési összefüggés alapján , amelyet néha "Relationship Aitken " -nek hívnak, és valójában a XVIII . Századi japán matematikus, Yoshisuke Matsunaga miatt: $B _ {{n + 1}} = \ összeg _ {{k = 0}} ^ {{n}} {n \ válassza k} B_ {k},$ ami a következőképpen bizonyítható:
Miután rögzítettünk egy x elemet egy n + 1 elemű halmazban, a partíciókat az x-et tartalmazó részen kívüli elemek k- száma szerint rendezzük . Minden k értéke 0-tól n- ig értékéhez tehát k elemet kell választanunk az x- től eltérő n elem közül , majd megadunk nekik egy partíciót.
A hét kisebb Bell számok első olyan B 2 = 2, B 3 = 5, B 7 = 877, B 13 = 27.644.437, B 42 = 35 742 549 198 872 617 291 353 508 656 626 642 567, B 55 = 359 334 085 968 622 831 041 960 188 598 043 661 065 388 726 959 079 837 és B 2841 (lásd az OEIS A051131 és A051130 készleteit ). Nem ismert, hogy vannak-e mások.

Generátor sorozat

Az összes Bell szám kezeléséhez megnézhetjük a hozzájuk tartozó generátor és exponenciális generátor sorozatot :

G (X) = \ összeg _ {n} B_ {n} X ^ {n} {\ text {és}} E (X) = \ összeg _ {n} {\ frac {B_ {n}} {n! }} X ^ {n} = 1 + X + 2 {\ frac {X ^ {2}} {2!}} + 5 {\ frac {X ^ {3}} {3!}} + 15 {\ frac {X ^ {4}} {4!}} + \ Ldots

Az első például tanulmányozására használható kongruencia osztályok az . Ami a második formális sorozatot illeti , kielégíti a differenciálegyenletet : ez látható a megismétlődési képlet $B_ {n}$ $E '(X) = {\ mathrm {e}} ^ {X} E (X)$

{\ displaystyle {\ frac {B_ {n + 1}} {n!}} = \ sum _ {k + l = n} {\ frac {1} {k!}} {\ frac {B_ {l}} {l!}} ~.}

Arra a következtetésre jutunk , hogy egyenlő egy szorzó szorzóval (amelyet az állandó kifejezés azonosításával találunk meg): ${\ mathrm {e}} ^ {{{\ mathrm {e}} ^ {X}}}$

E (X) = {\ mathrm {e}} ^ {{{\ \ mathrm {e}} ^ {X} -1}}.

Az együtthatók azonosítása a Dobinski-képlethez vezet :

B_ {n} = {\ frac {1} {{\ mathrm {e}}}} \ sum _ {{k = 0}} ^ {\ infty} {\ frac {k ^ {n}} {k!} }

amely a pillanata sorrendben N egy Poisson eloszlás paraméterrel 1.

Egyéb tulajdonságok

Ők is eleget Touchard kongruencia : ha p jelentése minden prímszám , akkor

B _ {{p + n}} \ equiv B_ {n} + B _ {{n + 1}} \ mod p.

Minden harangszám a második fajta Stirling-számok összege :

{\ displaystyle B_ {n} = \ sum _ {k = 0} ^ {n} S (n, k) = \ sum _ {k = 0} ^ {n} \ balra \ {{\ begin {mátrix} n \\ k \ end {mátrix}} \ jobb \}.}

A Bell-számokhoz számos aszimptotikus képlet ismert; egyikük az

B_ {n} \ sim {\ frac {1} {{{\ sqrt n}}}} \ balra [{{\ frac {n} {W (n)}}} \ jobbra] ^ {{n + {\ frac {1} {2}}}} e ^ {{{\ frac {n} {W (n)}} - n-1}},

ahol W jelentése Lambert W függvény ; kevésbé pontos közelítést kapunk, de kényelmesebb használni a keretezés segítségével ; észrevehető az előző közelítés hasonlósága a Stirling-képlettel . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Lásd is

A rendezett Bell-számok azonosítják a rendezett partíciókat.
A Bell háromszög , amely lehetővé teszi a Bell számok egyszerű megszerzését

Megjegyzések és hivatkozások

A halmaz elemei a szokásos halmazelméletben mindig megkülönböztethetők , de a multiset elméletben ez nem így van . És egy n megkülönböztethetetlen elemet tartalmazó halmaz partícióinak száma az egész szám partícióinak száma .
(in) AC Aitken , " Probléma kombinációkban " , Matematikai megjegyzések , 1. köt. 28,1933. január, xviii - xxiii ( ISSN 1757-7489 és 2051-204X , DOI 10.1017 / S1757748900002334 , online olvasás , hozzáférés : 2021. május 29. )
Donald Knuth , A számítógépes programozás művészete : A kombinatorikus generáció története , vol. 4, fasc. 4, Addison Wesley,2010
Daniel Barsky és Bénali Benzaghou , " Harangszámok és a tényleges összegek ", Journal de Théorie des Nombres de Bordeaux , vol. 16,2004, P. 1–17 ( olvassa el online [PDF] )
fogjuk találni más közelítések B n az (a) Eric W. Weisstein , " Bell száma " a mathworld .

Bibliográfia

Donald Knuth , A számítógépes programozás művészete : A kombinatorikus generáció története , vol. 4, fasc. 3, Addison Wesley,2010