Bell nummer

I matematikk , den n- te Bell nummer (oppkalt etter Eric Temple Bell ) er antallet av partisjoner av et sett med n distinkte elementer , eller, hva som utgjør det samme, antall Ekvivalensrelasjon på et slikt sett.

Første eiendommer

Disse tallene danner sekvensen av heltall A000110 fra OEIS , hvis første vilkår kan beregnes for hånd: $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$ Den første er verdt 1 fordi det er nøyaktig en partisjon av det tomme settet : den tomme partisjonen, som består av ingen deler. Faktisk er dens elementer (siden det ikke er noen) faktisk ikke-tomme og løsrev to og to, og av tomme forening.
De partisjoner er , og de tre partisjoner av den typen . ${\ displaystyle B_ {3} = 5}$ $\ {ABC \}$ ${\ displaystyle \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ displaystyle \ {\ {a, b, c \} \}}$ ${\ displaystyle \ {\ {a \}, \ {b, c \} \}}$
Bell tallene kan også beregnes trinnvis ved tilbakefall forhold følger, noen ganger kalt "Forholdet Aitken " og faktisk på grunn av den japanske matematikeren av XVIII th århundre Yoshisuke Matsunaga: $B _ {{n + 1}} = \ sum _ {{k = 0}} ^ {{n}} {n \ velg k} B_ {k},$ som kan demonstreres som følger:
Etter å ha fikset et element x i et sett med n + 1-elementer, sorterer vi partisjonene etter antall k av elementer utenfor delen som inneholder x .
For hver verdi av k fra 0 til n , er det derfor nødvendig å velge k- elementer blant n- elementene som er forskjellige fra x , og deretter gi en partisjon.
De syv mindre ringetallene først er B 2 = 2, B 3 = 5, B 7 = 877, B 13 = 27644437, B 42 = 35 742549 198 872617291353508656626642567 , B 55 = 359334085 968 622 831 041960 188 598 043 661 065 388 726 959 079 837 og B 2841 (se suitene A051131 og A051130 fra OEIS). Det er ikke kjent om det er andre.

Generatorserie

For å håndtere alle Bell-tallene, kan vi se på de tilhørende generator- og eksponensielle generatorseriene , som er henholdsvis:

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

Den første brukes for eksempel til å studere kongruensklassene til . Når det gjelder den andre formelle serien , tilfredsstiller den differensiallikningen : Dette kan sees ved å skrive gjentakelsesformelen i form $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!}} ~.}

Vi utleder at den er lik en multiplikasjonskonstant i nærheten (som vi finner ved identifisering av den konstante termen): ${\ mathrm {e}} ^ {{{\ mathrm {e}} ^ {X}}}$

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

Identifiseringen av koeffisientene fører til Dobinski-formelen :

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

som er øyeblikkets rekkefølge n av en Poisson-fordeling med parameter 1.

Andre egenskaper

De tilfredsstiller også Touchard- kongruens : hvis p er noe primtal da

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

Hvert bjellenummer er en sum av Stirling-nummer av den andre typen :

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

Flere asymptotiske formler for Bell-tall er kjent; en av dem er

B_ {n} \ sim {\ frac {1} {{{\ sqrt n}}}} \ venstre [{{\ frac {n} {W (n)}}} \ høyre] ^ {{n + {\ frac {1} {2}}}} e ^ {{{\ frac {n} {W (n)}} - n-1}},

hvor W er Lamberts W-funksjon ; en mindre presis tilnærming oppnås, men mer praktisk å bruke, ved hjelp av innrammingen ; man kan også merke likheten med den foregående tilnærmingen med formelen til Stirling . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Se også

De Bell tall bestilt , som identifiserer de bestilte partisjoner.
The Bell trekant , som gjør at du kan bare få Bell tall

Merknader og referanser

Elementene til et sett er alltid forskjellige i vanlig mengdeori , men dette er ikke tilfelle i multisettteori . Og antall partisjoner av et sett med n skille elementer er antall partisjoner av et helt tall .
(in) AC Aitken , " A Problem in Combinations " , Mathematical Notes , Vol. 28,Januar 1933, xviii - xxiii ( ISSN 1757-7489 og 2051-204X , DOI 10.1017 / S1757748900002334 , lest online , åpnet 29. mai 2021 )
Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , vol. 4, fasc. 4, Addison Wesley,2010
Daniel Barsky og Bénali Benzaghou , " Bell numbers and sum of factorials ", Journal de Théorie des Nombres de Bordeaux , vol. 16,2004, s. 1-17 ( les online [PDF] )
Vi finner andre tilnærminger B n på (in) Eric W. Weisstein , " Bell Number " på MathWorld .

Bibliografi

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