Numărul soneriei

În matematică , al n- lea număr de clopot (numit după Eric Temple Bell ) este numărul de partiții ale unei mulțimi cu n elemente distincte sau, ceea ce echivalează cu același număr de relații de echivalență pe un astfel de set.

Primele proprietăți

Aceste numere formează secvența numerelor întregi A000110 din OEIS , ai căror primi termeni pot fi calculați manual: $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$ Primul valorează 1, deoarece există exact o partiție a setului gol : partiția goală, formată din părți. Într-adevăr, elementele sale (întrucât nu există) sunt într-adevăr non-goale și disjuncte câte două, și de uniune goală.
Cele partițiile sunt , iar cele trei partiții de tip . ${\ displaystyle B_ {3} = 5}$ $\ {ABC \}$ ${\ displaystyle \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ displaystyle \ {\ {a, b, c \} \}}$ ${\ displaystyle \ {\ {a \}, \ {b, c \} \}}$
Numerele Bell pot fi calculate și pas cu pas după relația de recurență care urmează, uneori numită „Relația Aitken ” și, de fapt, datorită matematicianului japonez din secolul al XVIII- lea Yoshisuke Matsunaga: $B _ {{n + 1}} = \ sum _ {{k = 0}} ^ {{n}} {n \ alege k} B_ {k},$ care poate fi demonstrat după cum urmează:
După ce am fixat un element x într-un set cu n + 1 elemente, sortăm partițiile în funcție de numărul k de elemente din afara părții care conține x .
Pentru fiecare valoare a lui k de la 0 la n , trebuie deci să alegem k elemente dintre n elemente diferite de x , apoi să le oferim o partiție.
Cele șapte numere mai mici ale Bell sunt mai întâi B 2 = 2, B 3 = 5, B 7 = 877, B 13 = 27644437, 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 și B 2841 (a se vedea suitele A051131 și A051130 ale OEIS). Nu se știe dacă există altele.

Seria generatorului

Pentru a gestiona toate numerele Bell, ne putem uita la generatorul asociat și seriile generatoare exponențiale , care sunt respectiv:

G (X) = \ sum _ {n} B_ {n} X ^ {n} {\ text {și}} E (X) = \ sum _ {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

Primul este de exemplu folosit pentru a studia clasele de congruență ale . În ceea ce privește a doua serie formală , aceasta satisface ecuația diferențială : acest lucru poate fi văzut scriind formula recurenței în forma $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!}} ~.}

Deducem că este egală cu o constantă multiplicativă apropiată (pe care o găsim prin identificarea termenului constant): ${\ mathrm {e}} ^ {{{\ mathrm {e}} ^ {X}}}$

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

Identificarea coeficienților conduce la formula Dobinski :

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

care este momentul de ordine n al unei distribuții Poisson cu parametrul 1.

Alte proprietăți

De asemenea, satisfac congruența lui Touchard : dacă p este orice număr prim atunci

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

Fiecare număr Bell este o sumă a numerelor Stirling de al doilea fel :

{\ displaystyle B_ {n} = \ sum _ {k = 0} ^ {n} S (n, k) = \ sum _ {k = 0} ^ {n} \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}.}

Sunt cunoscute mai multe formule asimptotice pentru numerele Bell; unul dintre ei este

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

unde W este funcția W a lui Lambert ; se obține o aproximare mai puțin precisă, dar mai convenabilă de utilizat, cu ajutorul încadrării ; se poate observa, de asemenea, asemănarea aproximării precedente cu formula lui Stirling . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Vezi și tu

Cele Numerele Bell comandate , care identifică partițiile comandate.
Bell triunghiul , care vă permite să obțineți pur și simplu numerele Bell

Note și referințe

Elementele unui set sunt întotdeauna distincte în teoria obișnuită a mulțimilor , dar acest lucru nu este cazul în teoria multiset . Și, numărul de partiții ale unui set cu n elemente nedistinguibile este numărul de partiții ale unui număr întreg .
(în) AC Aitken , „ O problemă în combinații ” , Note matematice , Vol. 28,Ianuarie 1933, xviii - xxiii ( ISSN 1757-7489 și 2051-204X , DOI 10.1017 / S1757748900002334 , citit online , accesat la 29 mai 2021 )
Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , vol. 4, fasc. 4, Addison Wesley,2010
Daniel Barsky și Benali Benzaghou , " numere Bell și suma factorialele ", Journal de Theorie des Nombres de Bordeaux , vol. 16,2004, p. 1-17 ( citiți online [PDF] )
Vom găsi alte aproximări B n pe (în) Eric W. Weisstein , „ Bell Number ” pe MathWorld .

Bibliografie

Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , vol. 4, fasc. 3, Addison Wesley,2010