direita|miniaturadaimagem|349x349px| As 15 partições de um conjunto de 4 elementos ordenados em um diagrama de Hasse Existem S(4,1), ... , S (4, 4) = 1, 7, 6, 1 partições contendo 1, 2, 3, 4 conjuntos. Em matemática, particularmente em combinatória, um número de Stirling do segundo tipo (ou número de partição de Stirling) é o número de maneiras de particionar um conjunto de n objetos em k subconjuntos não vazios e é denotado por ou .Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison–Wesley, Reading MA. , p. 244. Os números de Stirling do segundo tipo ocorrem no campo da matemática chamado combinatória e no estudo de partições. Eles receberam o nome de James Stirling.

Definição

Os números de Stirling do segundo tipo, escritos ou ou com outras notações, conta a quantidade de maneiras de particionar um conjunto de objetos rotulados em subconjuntos não vazios não rotulados. De forma equivalente, eles contam o número de diferentes relações de equivalência com classes de equivalência que podem ser definidas em um elemento de conjunto . De fato, há uma bijeção entre o conjunto de partições e o conjunto de relações de equivalência em um determinado conjunto. Obviamente,

para n ≥ 0, e para n ≥ 1,

como a única maneira de particionar um conjunto de n elementos em n partes é colocar cada elemento do conjunto em sua própria parte, e a única maneira de particionar um conjunto não vazio em uma parte é colocar todos os elementos na mesma parte. Ao contrário dos números de Stirling do primeiro tipo, eles podem ser calculados usando uma fórmula de soma única:

Os números de Stirling do primeiro tipo podem ser caracterizados como os números que surgem quando se expressam potências de um x indeterminado em termos de fatoriais decrescentesConfusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.

(Em particular, (x)0=1 porque é um produto vazio).

Os números de Stirling do segundo tipo satisfazem a relação

Notação Várias notações foram usadas para números de Stirling do segundo tipo. A notação de chaves foi usado por Imanuel Marx e Antonio Salmeri em 1962 para variantes desses números.Transformation of Series by a Variant of Stirling's Numbers, Imanuel Marx, The American Mathematical Monthly 69, #6 (June–July 1962), pp. 530–532, .Antonio Salmeri, Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962), pp. 44–54. Isso levou Knuth a usá-lo, como mostrado aqui, no primeiro volume de The Art of Computer Programming (1968).Donald E. Knuth, Fundamental Algorithms, Reading, Mass.: Addison–Wesley, 1968. De acordo com a terceira edição de The Art of Computer Programming, esta notação também foi usada anteriormente por Jovan Karamata em 1935.p. 66, Donald E. Knuth, Fundamental Algorithms, 3rd ed., Reading, Mass.: Addison–Wesley, 1997.Jovan Karamata, Théorèmes sur la sommabilité exponentielle et d'autres sommabilités s'y rattachant, Mathematica (Cluj) 9 (1935), pp, 164–178. A notação foi usada por Richard Stanley em seu livro Enumerative Combinatorics e também, muito antes, por muitos outros escritores.

As notações usadas nesta página para números de Stirling não são universais e podem entrar em conflito com notações de outras fontes.

Relação com os números de Bell Desde o número de Stirling conta partições definidas de um conjunto de n elementos em k partes, a soma

sobre todos os valores de k é o número total de partições de um conjunto com n membros. Este número é conhecido como o n- ésimo número de Bell .

Analogamente, os números de Bell ordenados podem ser calculados a partir dos números de Stirling do segundo tipo via

Tabela de valores Abaixo está uma matriz triangular de valores para os números de Stirling do segundo tipo : 01234567891001101201130131401761501152510160131906515170163301350140211801127966170110502662819012553025777069512646462361100151193303410542525228275880750451 Assim como os coeficientes binomiais, esta tabela poderia ser estendida para , mas todas as entradas seriam 0.

Propriedades

Relação de recorrência Os números de Stirling do segundo tipo obedecem à relação de recorrência

com condições iniciais

Por exemplo, o número 25 na coluna k = 3 e linha n = 5 é dado por 25 = 7 + (3×6), onde 7 é o número acima e à esquerda de 25, 6 é o número acima de 25 e 3 é a coluna que contém o 6.

Para provar esta recorrência, observe que uma partição dos objetos em subconjuntos não vazios ou contém o -ésimo objeto como um elemento único ou não. O número de maneiras pelas quais o elemento único é um dos subconjuntos é dado por

já que devemos particionar os objetos restantes nos disponíveis subconjuntos. No outro caso o -ésimo objeto pertence a um subconjunto contendo outros objetos. O número de maneiras é dado por

já que particionamos todos os objetos, exceto o -ésimo em k subconjuntos, e então ficamos com k opções para inserir o objeto . A soma desses dois valores fornece o resultado desejado.

Outra relação de recorrência é dada por

que decorre da avaliação no .

Identidades simples Algumas identidades simples incluem

Isso ocorre porque dividir n elementos em conjunto significa necessariamente dividi-lo em um conjunto de tamanho 2 e conjuntos de tamanho 1. Portanto, precisamos apenas escolher esses dois elementos;

e

Para ver isso, primeiro observe que há 2 pares ordenados de subconjuntos complementares A e B. Em um caso, A é vazio e, em outro, B é vazio, então restam pares ordenados de subconjuntos. Por fim, como queremos pares não ordenados em vez de pares ordenados, dividimos esse último número por 2, obtendo o resultado acima.

Outra expansão explícita da relação de recorrência fornece identidades na mesma forma do exemplo acima.

Identidades A tabela na seção 6.1 de Matemática Concreta fornece uma infinidade de formas generalizadas de somas finitas envolvendo os números de Stirling. Várias somas finitas relevantes para este artigo incluem

Fórmula explícita Os números de Stirling do segundo tipo são dados pela fórmula explícita:

Isso pode ser derivado usando inclusão-exclusão para contar as sobreposições de n a k e usando o fato de que o número dessas sobreposições é .

Além disso, esta fórmula é um caso especial da k-ésima diferença direta do monômio avaliado em x = 0:

Como os polinômios de Bernoulli podem ser escritos em termos dessas diferenças diretas, obtém-se imediatamente uma relação nos números de Bernoulli :

A avaliação do exponencialmente incompleto polinômio de Bell Bn,k(x1, x2, ...) na sequência de 1's é igual a um número de Stirling do segundo tipo:

Outra fórmula explícita fornecida no Manual de Funções Matemáticas do NIST é

Paridade direita|miniaturadaimagem|256x256px| Paridade dos números de Stirling do segundo tipo A paridade de um número de Stirling do segundo tipo é a mesma que a paridade de um coeficiente binomial relacionado:

onde

onde denota o resto da divisão inteira de a por b.

Essa relação é especificada pelo mapeamento das coordenadas n e k no triângulo de Sierpiński.

Mais diretamente, deixe dois conjuntos conterem posições de 1's em representações binárias de resultados de expressões respectivas:

É possível imitar uma operação AND bit a bit interseccionando esses dois conjuntos:

onde denota o resto da divisão inteira de a por b;

para obter a paridade de um número de Stirling de segunda espécie em tempo O (1). Em pseudocódigo:

onde denota a divisão inteira de por ;

onde é o colchete de Iverson.

A paridade de um número Stirling central do segundo tipo é ímpar se e somente se é um número fibinário, um número cuja representação binária não possui dois 1s consecutivos.

Gerando funções Para um inteiro fixo n, a função geradora ordinária para números de Stirling do segundo tipo é dada por

onde são polinômios de Touchard. Se somarmos os números de Stirling em relação ao fatorial decrescente, podemos mostrar as seguintes identidades, entre outras:

e

que tem como caso especial

Para um inteiro fixo k, os números de Stirling do segundo tipo têm função geradora ordinária racional

e tem uma função geradora exponencial dada por

Uma função geradora bivariada mista para os números de Stirling do segundo tipo é

Limites inferior e superior Se e , então

Aproximação assintótica Para valor fixo de o valor assintótico dos números de Stirling do segundo tipo como é dado por

Se (onde o denota a pequena notação o ) então

L. C. Hsu, Note on an Asymptotic Expansion of the nth Difference of Zero, AMS Vol.19 NO.2 1948, pp. 273--277

Também existe uma aproximação uniformemente válida: para todo tal que , obtem-se

onde , e é a solução única para .N. M. Temme, Asymptotic Estimates of Stirling Numbers, STUDIES IN APPLIED MATHEMATICS 89:233-243 (1993), Elsevier Science Publishing. O erro relativo é limitado por cerca de .

Uni-modalidade Para fixo , é uni-modal, ou seja, a sequência aumenta e depois diminui. O máximo é atingido para no máximo dois valores consecutivos de k. Ou seja, existe um inteiro tal que

Olhando para a tabela de valores acima, os primeiros valores para são

Quando é grande

o valor máximo do número de Stirling pode ser aproximado com

Aplicações

Momentos da distribuição de Poisson Se X é uma variável aleatória com uma distribuição de Poisson com valor esperado λ, então seu n -ésimo momento é

Em particular, o n-ésimo momento da distribuição de Poisson com valor esperado 1 é precisamente o número de partições de um conjunto de tamanho n, ou seja, é o n-ésimo número de Bell (este fato é a fórmula de Dobiński ).

Momentos de pontos fixos de permutações aleatórias Seja a variável aleatória X o número de pontos fixos de uma permutação aleatória uniformemente distribuída de um conjunto finito de tamanho m. Então o n-ésimo momento de X é

Observação: O limite superior da soma é m, não n.

Em outras palavras, o n-ésimo momento dessa distribuição de probabilidade é o número de partições de um conjunto de tamanho n em não mais que m partes. Isso é provado no artigo sobre estatísticas de permutação aleatória, embora a notação seja um pouco diferente.

Esquemas de rima Os números de Stirling do segundo tipo podem representar o número total de esquemas de rima para um poema de n linhas. fornece o número de métricas possíveis para n linhas usando k sílabas rimadas únicas. Por exemplo, para um poema de 3 versos, há 1 esquema de rima usando apenas uma rima (aaa), 3 esquemas de rima usando duas rimas (aab, aba, abb) e 1 esquema de rima usando três rimas (abc).

Variantes

Números de r-Stirling do segundo tipo O número r-Stirling do segundo tipo conta o número de partições de um conjunto de n objetos em k subconjuntos disjuntos não vazios, de modo que os primeiros r elementos estejam em subconjuntos distintos.Broder, A. (1984). The r-Stirling numbers. Discrete Mathematics 49, 241-259 Esses números satisfazem a relação de recorrência

Algumas identidades combinatórias e uma conexão entre esses números e gramáticas livres de contexto podem ser encontradas em.Triana, J. (2022). r-Stirling numbers of the second kind through context-free grammars. Journal of automata, languages and combinatorics 27(4), 323-333

Números associados de Stirling do segundo tipo Um número de Stirling associado a r do segundo tipo é o número de maneiras de particionar um conjunto de n objetos em k subconjuntos, com cada subconjunto contendo pelo menos r elementos.L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222. É denotado por e obedece a relação de recorrência

Os números associados a 2 aparecem em outros lugares como "números de Ward" e como as magnitudes dos coeficientes dos polinômios de Mahler.

Números de Stirling reduzidos do segundo tipo