Número da campainha

Em matemática , o n- ésimo número de Bell (em homenagem a Eric Temple Bell ) é o número de partições de um conjunto com n elementos distintos ou, o que dá no mesmo, o número de relações de equivalência em tal conjunto.

Primeiras propriedades

Esses números formam a sequência de inteiros A000110 do OEIS , cujos primeiros termos podem ser calculados manualmente: $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$ O primeiro vale 1 porque há exatamente uma partição do conjunto vazio : a partição vazia, composta de nenhuma parte. De fato, seus elementos (já que não há nenhum) são de fato não vazios e disjuntos dois a dois, e de união vazia.
As partições são , e as três partições do tipo . ${\ displaystyle B_ {3} = 5}$ $\{ABC\}$ ${\ displaystyle \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ displaystyle \ {\ {a, b, c \} \}}$ ${\ displaystyle \ {\ {a \}, \ {b, c \} \}}$
Os números de Bell também pode ser calculado passo a passo pela relação de recorrência segue, às vezes chamado de "Relacionamento Aitken " e, na verdade, devido ao matemático japonês do XVIII ° século Yoshisuke Matsunaga: $B _ {{n + 1}} = \ sum _ {{k = 0}} ^ {{n}} {n \ escolha k} B_ {k},$ que pode ser demonstrado da seguinte forma:
Tendo fixado um elemento x em um conjunto com n + 1 elementos, classificamos as partições de acordo com o número k de elementos fora da parte que contém x .
Para cada valor de k de 0 a n , devemos, portanto, escolher k elementos entre os n elementos diferentes de x e , em seguida, dar-lhes uma partição.
Os sete números de sino menores primeiro são 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 e B 2841 (ver suites A051131 e A051130 do OEIS). Não se sabe se existem outros.

Série Gerador

Para lidar com todos os números de Bell, podemos olhar para o gerador associado e a série de gerador exponencial , que são respectivamente:

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

O primeiro é, por exemplo, usado para estudar as classes de congruência de . Quanto à segunda série formal , ela satisfaz a equação diferencial : isso pode ser visto escrevendo a fórmula de recorrência no formulário $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!}} ~.}

Deduzimos que é igual a uma constante multiplicativa próxima (que encontramos pela identificação do termo constante): ${\ mathrm {e}} ^ {{{\ mathrm {e}} ^ {X}}}$

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

A identificação dos coeficientes leva à fórmula de Dobinski :

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

que é o momento de ordem n de uma distribuição de Poisson com parâmetro 1.

Outras propriedades

Eles também satisfazem a congruência de Touchard : se p é qualquer número primo, então

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

Cada número de Bell é uma soma dos números de Stirling de segundo tipo :

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

Várias fórmulas assintóticas para números de Bell são conhecidas; uma delas é

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

onde W é a função W de Lambert ; uma aproximação menos precisa é obtida, mas mais conveniente de usar, com o auxílio do enquadramento ; também se pode notar a semelhança da aproximação anterior com a fórmula de Stirling . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Veja também

Os números de Bell ordenados , que identificam as partições ordenadas.
O triângulo de Bell , que permite que você simplesmente obtenha os números de Bell

Notas e referências

Os elementos de um conjunto são sempre distintos na teoria de conjuntos usual , mas este não é o caso na teoria de multisets . E, o número de partições de um conjunto com n elementos indistinguíveis é o número de partições de um inteiro .
(em) AC Aitken , " A Problem in Combinations " , Mathematical Notes , Vol. 28,Janeiro de 1933, xviii - xxiii ( ISSN 1757-7489 e 2051-204X , DOI 10.1017 / S1757748900002334 , ler online , acessado em 29 de maio de 2021 )
Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , vol. 4, fasc. 4, Addison Wesley,2010
Daniel Barsky e Bénali Benzaghou , " Números de sino e soma de fatoriais ", Journal de Théorie des Nombres de Bordeaux , vol. 16,2004, p. 1-17 ( leia online [PDF] )
Encontraremos outras aproximações B n em (em) Eric W. Weisstein , " Bell Number " em MathWorld .

Bibliografia

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