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 .[1] 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 S(n,k) ou ou com outras notações, conta a quantidade de maneiras de particionar um conjunto de n objetos rotulados em k subconjuntos não vazios não rotulados. De forma equivalente, eles contam o número de diferentes relações de equivalência com k classes de equivalência que podem ser definidas em um elemento de conjunto n. 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:[2]
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.[4][5] Isso levou Knuth a usá-lo, como mostrado aqui, no primeiro volume de The Art of Computer Programming (1968).[6][7] 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.[8][9] A notação S(n,k) foi usada por Richard Stanley em seu livro Enumerative Combinatorics e também, muito antes, por muitos outros escritores.[6]
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
Abaixo está uma matriz triangular de valores para os números de Stirling do segundo tipo (sequência A008277 na OEIS) :
k
n
0
1
2
3
4
5
6
7
8
9
10
0
1
1
0
1
2
0
1
1
3
0
1
3
1
4
0
1
7
6
1
5
0
1
15
25
10
1
6
0
1
31
90
65
15
1
7
0
1
63
301
350
140
21
1
8
0
1
127
966
1701
1050
266
28
1
9
0
1
255
3025
7770
6951
2646
462
36
1
10
0
1
511
9330
34105
42525
22827
5880
750
45
1
Assim como os coeficientes binomiais, esta tabela poderia ser estendida para k > n, 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 n + 1 objetos em k subconjuntos não vazios ou contém o (n + 1)-é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 n objetos restantes nos disponíveis k - 1 subconjuntos. No outro caso o (n + 1)-ésimo objeto pertence a um subconjunto contendo outros objetos. O número de maneiras é dado por
já que particionamos todos os objetos, exceto o (n + 1)-ésimo em k subconjuntos, e então ficamos com k opções para inserir o objeto n + 1 . 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 n − 1 conjunto significa necessariamente dividi-lo em um conjunto de tamanho 2 e n − 2 conjuntos de tamanho 1. Portanto, precisamos apenas escolher esses dois elementos;
e
Para ver isso, primeiro observe que há 2n pares ordenados de subconjuntos complementares A e B. Em um caso, A é vazio e, em outro, B é vazio, então restam 2n − 2 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:
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.[11]
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
Também existe uma aproximação uniformemente válida: para todo k tal que 1 < k < n, obtem-se
onde , e é a solução única para .[14] 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 0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, ...
Quando é grande
o valor máximo do número de Stirling pode ser aproximado com
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.[15] 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.[16]
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.[17] É denotado por e obedece a relação de recorrência
Os números associados a 2 (sequência A008299 na OEIS) 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
Denote os n objetos a serem particionados pelos inteiros 1, 2, ..., n. Defina os números de Stirling reduzidos do segundo tipo, denotados , para serem o número de maneiras de particionar os inteiros 1, 2, ..., n em k subconjuntos não vazios, de modo que todos os elementos em cada subconjunto tenham uma distância em pares de pelo menos d. Ou seja, para quaisquer inteiros i e j em um determinado subconjunto, é necessário que . Foi demonstrado que estes números satisfazem
(daí o nome "reduzido").[18] Observe (tanto pela definição quanto pela fórmula de redução) que , os familiares números de Stirling do segundo tipo.
↑Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.
↑Transformation of Series by a Variant of Stirling's Numbers, Imanuel Marx, The American Mathematical Monthly69, #6 (June–July 1962), pp. 530–532, JSTOR2311194.
↑Antonio Salmeri, Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962), pp. 44–54.
↑L. C. Hsu, Note on an Asymptotic Expansion of the nth Difference of Zero, AMS Vol.19 NO.2 1948, pp. 273--277
↑N. M. Temme, Asymptotic Estimates of Stirling Numbers, STUDIES IN APPLIED MATHEMATICS 89:233-243 (1993), Elsevier Science Publishing.
↑Broder, A. (1984). The r-Stirling numbers. Discrete Mathematics 49, 241-259
↑Triana, J. (2022). r-Stirling numbers of the second kind through context-free grammars. Journal of automata, languages and combinatorics 27(4), 323-333
↑L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
Boyadzhiev, Khristo (2012). «Close encounters with the Stirling numbers of the second kind». Mathematics Magazine. 85 (4): 252–266. arXiv:1806.09468. doi:10.4169/math.mag.85.4.252.