Número da campainha - Bell number

Na matemática combinatória , os números de Bell contam as partições possíveis de um conjunto . Esses números têm sido estudados por matemáticos desde o século 19 e suas raízes remontam ao Japão medieval. Em um exemplo da lei da eponímia de Stigler , eles foram nomeados em homenagem a Eric Temple Bell , que escreveu sobre eles na década de 1930.

Os números de sino são denotados por B _n , onde n é um número inteiro maior ou igual a zero . Começando com B ₀ = B ₁ = 1, os primeiros números da campainha são

1, 1, 2, 5, 15, 52, 203, 877, 4140, ... (sequência A000110 no OEIS ).

O número de Bell B _n conta o número de maneiras diferentes de particionar um conjunto que tem exatamente n elementos ou, de maneira equivalente, o número de relações de equivalência sobre ele. B _n também conta o número de esquemas de rima diferentes para poemas de n linhas.

Além de aparecerem em problemas de contagem, esses números têm uma interpretação diferente, como momentos de distribuição de probabilidade . Em particular, B _n representa o n th momento de uma distribuição de Poisson com média 1.

Contando

Definir partições

As partições de conjuntos podem ser organizadas em uma ordem parcial, mostrando que cada partição de um conjunto de tamanho n "usa" uma das partições de um conjunto de tamanho n-1.

As 52 partições de um conjunto com 5 elementos

Em geral, B _n é o número de partições de um conjunto de tamanho n . Uma partição de um conjunto S é definido como uma família de não-vazia, subconjuntos disjuntos de pares de S , cuja união é S . Por exemplo, B ₃  = 5 porque o conjunto de 3 elementos { a ,  b ,  c } pode ser particionado de 5 maneiras distintas:

{{ a }, { b }, { c }}

{{ a }, { b , c }}

{{ b }, { a , c }}

{{ c }, { a , b }}

{{ a , b , c }}.

Conforme sugerido pela notação de conjunto acima, a ordem dos subconjuntos dentro da família não é considerada; as partições ordenadas são contadas por uma sequência diferente de números, os números de Bell ordenados . B ₀ é 1 porque há exatamente uma partição do conjunto vazio . Esta partição é ela própria o conjunto vazio; ele pode ser interpretado como uma família de subconjuntos do conjunto vazio, consistindo em zero subconjuntos. É verdade que todos os subconjuntos nesta família são subconjuntos não vazios do conjunto vazio e que são subconjuntos disjuntos em pares do conjunto vazio, porque não há subconjuntos com essas propriedades improváveis.

As partições de um conjunto correspondem um a um com suas relações de equivalência . Essas são relações binárias que são reflexivas , simétricas e transitivas . A relação de equivalência correspondente a uma partição define dois elementos como equivalentes quando pertencem ao mesmo subconjunto de partição que o outro. Por outro lado, toda relação de equivalência corresponde a uma partição em classes de equivalência . Portanto, os números de Bell também contam as relações de equivalência.

Factorizações

Se um número N é um squarefree positivo inteiro (o que significa que é o produto de um número n de distintos números primos ), então B _n indica o número de diferentes partições multiplicativos de N . Essas são fatorações de N em números maiores que um, tratando duas fatorações como iguais se tiverem os mesmos fatores em uma ordem diferente. Por exemplo, 30 é o produto dos três primos 2, 3 e 5, e tem B ₃ = 5 fatorações:

${\ displaystyle 30 = 2 \ vezes 15 = 3 \ vezes 10 = 5 \ vezes 6 = 2 \ vezes 3 \ vezes 5}$

Esquemas de rima

Os números de Bell também contam os esquemas de rima de um poema ou estrofe de n linhas . Um esquema de rima descreve quais linhas rimam entre si e, portanto, pode ser interpretado como uma partição do conjunto de linhas em subconjuntos rimados. Os esquemas de rima são geralmente escritos como uma sequência de letras romanas, uma por linha, com as linhas de rima dadas as mesmas letras umas das outras e com as primeiras linhas de cada conjunto de rimas rotuladas em ordem alfabética. Assim, os 15 esquemas de rima de quatro linhas possíveis são AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC e ABCD.

Permutações

Os números de Bell surgem em um problema de embaralhamento de cartas mencionado no adendo a Gardner (1978) . Se um baralho de n cartas é embaralhado removendo repetidamente a carta do topo e reinserindo-a em qualquer lugar do baralho (incluindo sua posição original no topo do baralho), com exatamente n repetições desta operação, então há n ⁿ embaralhamentos diferentes que pode ser realizado. Destes, o número que retorna o baralho à sua ordem de classificação original é exatamente B _n . Assim, a probabilidade de que o baralho esteja em sua ordem original após embaralhá-lo dessa maneira é B _n / n ⁿ , que é significativamente maior do que 1 / n ! probabilidade que descreveria uma permutação uniformemente aleatória do baralho.

Relacionados ao embaralhamento de cartas estão vários outros problemas de contagem de tipos especiais de permutações que também são respondidos pelos números de Bell. Por exemplo, o n- ésimo número de Bell é igual ao número de permutações em n itens nos quais nenhum dos três valores ordenados possui os dois últimos desses três consecutivos. Em uma notação para padrões de permutação generalizados , onde os valores que devem ser consecutivos são escritos adjacentes uns aos outros, e os valores que podem aparecer não consecutivamente são separados por um travessão, essas permutações podem ser descritas como as permutações que evitam o padrão 1-23. As permutações que evitam os padrões generalizados 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 e 23-1 também são contadas pelos números de Bell. As permutações nas quais cada padrão 321 (sem restrição de valores consecutivos) pode ser estendido para um padrão 3241 também são contadas pelos números de Bell. No entanto, os números de Bell crescem muito rapidamente para contar as permutações que evitam um padrão que não foi generalizado desta forma: pela (agora comprovada) conjectura de Stanley-Wilf , o número de tais permutações é unicamente exponencial, e os números de Bell têm uma maior taxa de crescimento assintótico do que isso.

Esquema de triângulo para cálculos

A matriz triangular cuja sequência diagonal direita consiste em números de Bell

Os números de Bell pode ser facilmente calculado através da criação do chamado triângulo de Bell , também chamada gama de Aitken ou o triângulo Peirce após Alexander Aitken e Charles Sanders Peirce .

1. Comece com o número um. Coloque isso em uma linha por si só. ( )${\ displaystyle x_ {0,1} = 1}$
2. Comece uma nova linha com o elemento mais à direita da linha anterior como o número mais à esquerda ( onde r é o último elemento da ( i -1) -ésima linha)${\ displaystyle x_ {i, 1} \ leftarrow x_ {i-1, r}}$
3. Determine os números que não estão na coluna da esquerda tomando a soma do número à esquerda e o número acima do número à esquerda, ou seja, o número diagonalmente acima e à esquerda do número que estamos calculando ${\ displaystyle (x_ {i, j} \ leftarrow x_ {i, j-1} + x_ {i-1, j-1})}$
4. Repita a etapa três até que haja uma nova linha com mais um número do que a linha anterior (execute a etapa 3 até )${\ displaystyle j = r + 1}$
5. O número do lado esquerdo de uma determinada linha é o número do sino dessa linha. ( )${\ displaystyle B_ {i} \ leftarrow x_ {i, 1}}$

Aqui estão as primeiras cinco linhas do triângulo construído por estas regras:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

Os números do sino aparecem nos lados esquerdo e direito do triângulo.

Propriedades

Fórmulas de soma

Os números de Bell satisfazem uma relação de recorrência envolvendo coeficientes binomiais :

${\ displaystyle B_ {n + 1} = \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} B_ {k}.}$

Isso pode ser explicado observando que, de uma partição arbitrária de n  + 1 itens, a remoção do conjunto contendo o primeiro item deixa uma partição de um conjunto menor de k itens para algum número k que pode variar de 0 a n . Existem opções para os k itens que permanecem após a remoção de um conjunto e B _k opções de como particioná-los. ${\ displaystyle {\ tbinom {n} {k}}}$

Uma fórmula de soma diferente representa cada número de Bell como uma soma dos números de Stirling do segundo tipo

${\ displaystyle B_ {n} = \ sum _ {k = 0} ^ {n} \ esquerda \ {{n \ sobre k} \ direita \}.}$

O número de Stirling é o número de maneiras de particionar um conjunto de cardinalidade n em exatamente k subconjuntos não vazios. Assim, na equação que relaciona os números de Bell aos números de Stirling, cada partição contada no lado esquerdo da equação é contada em exatamente um dos termos da soma no lado direito, aquele para o qual k é o número de conjuntos na partição. ${\ displaystyle \ left \ {{n \ atop k} \ right \}}$

Spivey (2008) forneceu uma fórmula que combina essas duas somas:

${\ displaystyle B_ {n + m} = \ sum _ {k = 0} ^ {n} \ sum _ {j = 0} ^ {m} \ left \ {{m \ atop j} \ right \} {n \ escolha k} j ^ {nk} B_ {k}.}$

Função geradora

A função de geração exponencial dos números de Bell é

${\ displaystyle B (x) = \ sum _ {n = 0} ^ {\ infty} {\ frac {B_ {n}} {n!}} x ^ {n} = e ^ {e ^ {x} - 1}.}$

Nesta fórmula, a soma do meio é a forma geral usada para definir a função de geração exponencial para qualquer sequência de números, e a fórmula à direita é o resultado de realizar a soma no caso específico dos números de Bell.

Uma forma de derivar esse resultado usa a combinatória analítica , um estilo de raciocínio matemático no qual conjuntos de objetos matemáticos são descritos por fórmulas que explicam sua construção a partir de objetos mais simples e, em seguida, essas fórmulas são manipuladas para derivar as propriedades combinatórias dos objetos. Na linguagem da combinatória analítica, uma partição de conjunto pode ser descrita como um conjunto de urnas não vazias nas quais os elementos rotulados de 1 an foram distribuídos, e a classe combinatória de todas as partições (para todos os n ) pode ser expressa pela notação

${\ displaystyle \ mathrm {S \ scriptstyle ET} (\ mathrm {S \ scriptstyle ET} _ {\ geq 1} ({\ mathcal {Z}})).}$

Aqui, está uma classe combinatória com apenas um único membro de tamanho um, um elemento que pode ser colocado em uma urna. O operador interno descreve um conjunto ou urna que contém um ou mais elementos rotulados, e o externo descreve a partição geral como um conjunto dessas urnas. A função de geração exponencial pode então ser lida a partir desta notação, traduzindo o operador na função exponencial e a restrição de não-vazio ≥1 em subtração por um. ${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle \ mathrm {S \ scriptstyle ET} _ {\ geq 1}}$${\ displaystyle \ mathrm {S \ scriptstyle ET}}$${\ displaystyle \ mathrm {S \ scriptstyle ET}}$

Um método alternativo para derivar a mesma função geradora usa a relação de recorrência para os números de Bell em termos de coeficientes binomiais para mostrar que a função geradora exponencial satisfaz a equação diferencial . A própria função pode ser encontrada resolvendo esta equação. ${\ displaystyle B '(x) = e ^ {x} B (x)}$

Distribuições de momentos de probabilidade

Os números de Bell satisfazem a fórmula de Dobinski

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

Essa fórmula pode ser derivada expandindo a função de geração exponencial usando a série de Taylor para a função exponencial e, em seguida, coletando termos com o mesmo expoente. Ele permite que B _n deve ser interpretado como o n th momento de uma distribuição de Poisson com valor esperado 1.

O n th número Bell é também a soma dos coeficientes no n th polinomial de Bell completo , que expressa o n th momento de qualquer distribuição de probabilidade , como uma função dos primeiros n cumulantes .

Aritmética modular

Os números de Bell obedecem à congruência de Touchard : Se p for qualquer número primo, então

${\ displaystyle B_ {p + n} \ equiv B_ {n} + B_ {n + 1} {\ pmod {p}}}$

ou generalizando

${\ displaystyle B_ {p ^ {m} + n} \ equiv mB_ {n} + B_ {n + 1} {\ pmod {p}}.}$

Por causa da congruência de Touchard, os números de Bell são módulo p periódico , para todo número primo p ; por exemplo, para p  = 2, os números de Bell repetem o padrão ímpar-ímpar-par com o período três. O período desta repetição, para um número primo arbitrário p , deve ser um divisor de

${\ displaystyle {\ frac {p ^ {p} -1} {p-1}}}$

e para todos os primos p ≤ 101 ep = 113, 163, 167 ou 173 é exatamente este número (sequência A001039 no OEIS ).

O período dos números de Bell ao módulo n são

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784753, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784123, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 8551271983 75718776648063, 117, 1.647.084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, 156, ... (sequência A054767 no OEIS )

Representação integral

Uma aplicação da fórmula integral de Cauchy à função geradora exponencial produz a representação integral complexa

${\ displaystyle B_ {n} = {\ frac {n!} {2 \ pi ie}} \ int _ {\ gamma} {\ frac {e ^ {e ^ {z}}} {z ^ {n + 1 }}} \, dz.}$

Algumas representações assintóticas podem então ser derivadas por uma aplicação padrão do método da descida mais íngreme .

Log-concavidade

Os números de Bell formam uma sequência logaritmicamente convexa . Dividindo-os pelos fatoriais, B _n / n !, Obtém-se uma sequência logaritmicamente côncava.

Taxa de crescimento

Várias fórmulas assintóticas para os números de Bell são conhecidas. Em Berend & Tassa (2010) os seguintes limites foram estabelecidos:

${\ displaystyle B_ {n} <\ left ({\ frac {0.792n} {\ ln (n + 1)}} \ right) ^ {n}}$para todos os inteiros positivos ;${\ displaystyle n}$

além disso, se para todos , ${\ displaystyle \ varepsilon> 0}$${\ displaystyle n> n_ {0} (\ varepsilon)}$

${\ displaystyle B_ {n} <\ left ({\ frac {e ^ {- 0,6+ \ varepsilon} n} {\ ln (n + 1)}} \ right) ^ {n}}$

onde e os números de Bell também podem ser aproximados usando a função Lambert W , uma função com a mesma taxa de crescimento do logaritmo, como ${\ displaystyle ~ n_ {0} (\ varepsilon) = \ max \ left \ {e ^ {4}, d ^ {- 1} (\ varepsilon) \ right \} ~}$${\ displaystyle ~ d (x): = \ ln \ ln (x + 1) - \ ln \ ln x + {\ frac {1 + e ^ {- 1}} {\ ln x}} \ ,.}$

${\ displaystyle B_ {n} \ sim {\ frac {1} {\ sqrt {n}}} \ left ({\ frac {n} {W (n)}} \ right) ^ {n + {\ frac {1 } {2}}} \ exp \ left ({\ frac {n} {W (n)}} - n-1 \ right).}$

Moser & Wyman (1955) estabeleceu a expansão

${\ displaystyle B_ {n + h} = {\ frac {(n + h)!} {W (n) ^ {n + h}}} \ times {\ frac {\ exp (e ^ {W (n) } -1)} {(2 \ pi B) ^ {1/2}}} \ times \ left (1 + {\ frac {P_ {0} + hP_ {1} + h ^ {2} P_ {2} } {e ^ {W (n)}}} + {\ frac {Q_ {0} + hQ_ {1} + h ^ {2} Q_ {2} + h ^ {3} Q_ {3} + h ^ { 4} Q_ {4}} {e ^ {2W (n)}}} + O (e ^ {- 3W (n)}) \ direita)}$

uniformemente para as , where e each e são expressões conhecidas em . ${\ displaystyle h = O (\ ln (n))}$${\ displaystyle n \ rightarrow \ infty}$${\ displaystyle B}$${\ displaystyle P_ {i}}$${\ displaystyle Q_ {i}}$${\ displaystyle W (n)}$

A expressão assintótica

${\ displaystyle {\ begin {alinhados} {\ frac {\ ln B_ {n}} {n}} & = \ ln n- \ ln \ ln n-1 + {\ frac {\ ln \ ln n} {\ ln n}} + {\ frac {1} {\ ln n}} + {\ frac {1} {2}} \ left ({\ frac {\ ln \ ln n} {\ ln n}} \ right) ^ {2} + O \ left ({\ frac {\ ln \ ln n} {(\ ln n) ^ {2}}} \ right) \\ & {} \ qquad {\ text {as}} n \ para \ infty \ end {alinhado}}}$

foi estabelecido por de Bruijn (1981) .

Bell primes

Gardner (1978) levantou a questão de saber se infinitos números de Bell também são números primos . Os primeiros números de Bell que são primos são:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (sequência A051131 no OEIS )

correspondendo aos índices 2, 3, 7, 13, 42 e 55 (sequência A051130 no OEIS ).

O próximo número primo de Bell é B ₂₈₄₁ , que é aproximadamente 9,30740105 × 10 ⁶⁵³⁸ . Em 2018, é o maior número de sino primo conhecido. Ignacio Larrosa Cañestro mostrou que era um provável primo em 2002. Após 17 meses de computação com o programa ECPP Primo de Marcel Martin , Ignacio Larrosa Cañestro provou que era um primo em 2004. Ele descartou qualquer outro possível primo abaixo de B ₆₀₀₀ , posteriormente estendido para B ₃₀₄₄₇ por Eric Weisstein . A pesquisa foi estendida ao B ₅₀₀₀₀ pela Vaclav Kotesovec (18/05/2021).

História

Os números de Bell são nomeados em homenagem a Eric Temple Bell , que escreveu sobre eles em 1938, seguindo um artigo de 1934 em que estudou os polinômios de Bell . Bell não afirmou ter descoberto esses números; em seu artigo de 1938, ele escreveu que os números de Bell "foram investigados com frequência" e "foram redescobertos muitas vezes". Bell cita várias publicações anteriores sobre esses números, começando com Dobiński (1877), que fornece a fórmula de Dobiński para os números de Bell. Bell chamou esses números de "números exponenciais"; o nome "números de sino" e a notação B _n para esses números foram dados a eles por Becker & Riordan (1948) .

A primeira enumeração exaustiva de partições definidas parece ter ocorrido no Japão medieval, onde (inspirado na popularidade do livro The Tale of Genji ) surgiu um jogo de salão chamado genji-ko , no qual os convidados recebiam cinco pacotes de incenso para cheirar e foram solicitados a adivinhar quais eram iguais e quais eram diferentes. As 52 soluções possíveis, contadas pelo Bell número B ₅ , foram registradas por 52 diagramas diferentes, que foram impressos acima dos títulos dos capítulos em algumas edições de The Tale of Genji.

No segundo caderno de Srinivasa Ramanujan , ele investigou tanto os polinômios de Bell quanto os números de Bell. As primeiras referências ao triângulo de Bell , que tem os números de Bell em ambos os lados, incluem Peirce (1880) e Aitken (1933) .

Veja também

• Polinômios de Touchard
• Numero catalão

Notas

Referências

links externos

• Robert Dickau. "Diagramas de números de sino" .
• Weisstein, Eric W. "Bell Number" . MathWorld .
• Gottfried Helms. "Outras propriedades e generalização de números de sino" (PDF) .