Números de Stirling do segundo tipo
# Números de Stirling do segundo tipo

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 $S(n,k)$ ou $\textstyle \left\{{n \atop k}\right\}$. 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 $\lbrace \textstyle {n \atop k}\rbrace$ 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,
    $\left\{{n \atop n}\right\}=1$ para n ≥ 0, e $\left\{{n \atop 1}\right\}=1$ 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:
    $\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}=\sum _{i=0}^{k}{\frac {(-1)^{k-i}i^{n}}{(k-i)!i!}}.$
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 decrescentes
    $(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$
(Em particular, (x)$_0$=1 porque é um produto vazio).
Os números de Stirling do segundo tipo satisfazem a relação
    $\sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}.$

## Notação

Várias notações foram usadas para números de Stirling do segundo tipo. A notação de chaves {n/k}{\textstyle \textstyle \lbrace {n \atop k}\rbrace } foi usado por Imanuel Marx e Antonio Salmeri em 1962 para variantes desses números. Isso levou Knuth a usá-lo, como mostrado aqui, no primeiro volume de The Art of Computer Programming (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. 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.
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 $\left\{{n \atop k}\right\}$ conta partições definidas de um conjunto de n elementos em k partes, a soma
    $B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}$
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
    $a_{n}=\sum _{k=0}^{n}k!\left\{{n \atop k}\right\}.$

## Tabela de valores

Abaixo está uma matriz triangular de valores para os números de Stirling do segundo tipo (sequência A008277 na OEIS) :
| kn | 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
    $\left\{{n+1 \atop k}\right\}=k\left\{{n \atop k}\right\}+\left\{{n \atop k-1}\right\}\quad {\text{, para}}\;0<k<n$
com condições iniciais
    $\left\{{n \atop n}\right\}=1\quad {\text{, para}}\;n\geq 0{\text{ ,}}\quad {\text{ e }}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0\quad {\text{, para }}n>0{\text{.}}$
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
    $\left\{{n \atop k-1}\right\}$
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
    $k\left\{{n \atop k}\right\}$
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
$\left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(k-r)!}}.$
que decorre da avaliação $\sum _{r=0}^{n}\left\{{n \atop r}\right\}(x)_{r}=x^{n}$ no $x=k$ .

### Identidades simples

Algumas identidades simples incluem
    $\left\{{n \atop n-1}\right\}={\binom {n}{2}}.$
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
    $\left\{{n \atop 2}\right\}=2^{n-1}-1.$
Para ver isso, primeiro observe que há 2$^n$ pares ordenados de subconjuntos complementares A e B. Em um caso, A é vazio e, em outro, B é vazio, então restam 2$^n$ − 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
    ${\begin{aligned}\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\}\\\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}(k+1)^{n-j}\left\{{j \atop k}\right\}\\\left\{{n+k+1 \atop k}\right\}&=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}\\\left\{{n \atop \ell +m}\right\}{\binom {\ell +m}{\ell }}&=\sum _{k}\left\{{k \atop \ell }\right\}\left\{{n-k \atop m}\right\}{\binom {n}{k}}\end{aligned}}$

### Fórmula explícita

Os números de Stirling do segundo tipo são dados pela fórmula explícita:
    $\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}=\sum _{j=0}^{k}{\frac {(-1)^{k-j}j^{n}}{(k-j)!j!}}.$
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 é k!{n/k}{\textstyle k!\left\{{n \atop k}\right\}} .
Além disso, esta fórmula é um caso especial da k-ésima diferença direta do monômio $x^{n}$ avaliado em x = 0:
    $\Delta ^{k}x^{n}=\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}(x+j)^{n}.$
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 :
    $B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.$
A avaliação do exponencialmente incompleto polinômio de Bell B$_{n,k}$(x$_1$, x$_2$, ...) na sequência de 1's é igual a um número de Stirling do segundo tipo:
    $\left\{{n \atop k}\right\}=B_{n,k}(1,1,\dots ,1).$
Outra fórmula explícita fornecida no Manual de Funções Matemáticas do NIST é
    $\left\{{n \atop k}\right\}=\sum _{\begin{array}{c}c_{1}+\ldots +c_{k}=n-k\\c_{1},\ldots ,\ c_{k}\ \geq \ 0\end{array}}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}$

### Paridade

A paridade de um número de Stirling do segundo tipo é a mesma que a paridade de um coeficiente binomial relacionado:
    $\left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},$ onde $z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .$
onde a mod b 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:
    ${\begin{aligned}\mathbb {A} :\ \sum _{i\in \mathbb {A} }2^{i}&=n-k,\\\mathbb {B} :\ \sum _{j\in \mathbb {B} }2^{j}&=\left\lfloor {\dfrac {k-1}{2}}\right\rfloor .\\\end{aligned}}$
É possível imitar uma operação AND bit a bit interseccionando esses dois conjuntos:
    ${\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset ;\end{cases}}$
onde a mod b 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:
    ${\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];$
onde a div b denota a divisão inteira de a por b;
onde $\left[b\right]$ é o colchete de Iverson.
A paridade de um número Stirling central do segundo tipo $\textstyle \left\{{2n \atop n}\right\}$ é ímpar se e somente se $n$ é 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 $\left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots$ é dada por
    $\sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),$
onde $T_{n}(x)$ 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:
    $\sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}$
e
    $\sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n},$
que tem como caso especial
    $\sum _{k=0}^{n}\left\{{n \atop k}\right\}(n)_{k}=n^{n}$
Para um inteiro fixo k, os números de Stirling do segundo tipo têm função geradora ordinária racional
    $\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{x^{k+1}(1/x)_{k+1}}}$
e tem uma função geradora exponencial dada por
    $\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.$
Uma função geradora bivariada mista para os números de Stirling do segundo tipo é
    $\sum _{k=0}^{\infty }\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.$

### Limites inferior e superior

Se $n\geq 2$ e $1\leq k\leq n-1$, então
    ${\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1\leq \left\{{n \atop k}\right\}\leq {\frac {1}{2}}{n \choose k}k^{n-k}$

### Aproximação assintótica

Para valor fixo de $k,$ o valor assintótico dos números de Stirling do segundo tipo como $n\rightarrow \infty$ é dado por
    $\left\{{n \atop k}\right\}{\underset {n\to \infty }{\sim }}{\frac {k^{n}}{k!}}.$
Se $k=o({\sqrt {n}})$ (onde o denota a pequena notação o ) então
    $\left\{{n+k \atop n}\right\}{\underset {n\to \infty }{\sim }}{\frac {n^{2k}}{2^{k}k!}}.$
Também existe uma aproximação uniformemente válida: para todo k tal que 1 < k < n, obtem-se
    $\left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),$
onde $v=n/k$, e $G\in (0,1)$ é a solução única para $G=ve^{G-v}$. O erro relativo é limitado por cerca de $0.066/n$ .

### Uni-modalidade

Para fixo $n$, $\left\{{n \atop k}\right\}$ é 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 $k_{n}$ tal que
    $\left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop k_{n}}\right\}\geq \left\{{n \atop k_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.$
Olhando para a tabela de valores acima, os primeiros valores para $k_{n}$ são 0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, ...
Quando $n$ é grande
    $k_{n}{\underset {n\to \infty }{\sim }}{\frac {n}{\log n}},$
o valor máximo do número de Stirling pode ser aproximado com
    $\log \left\{{n \atop k_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).$

## 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 é
    $E(X^{n})=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\lambda ^{k}.$
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 é
    $E(X^{n})=\sum _{k=0}^{m}\left\{{n \atop k}\right\}.$
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. $S(n,k)$ 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 $\left\{{n \atop k}\right\}_{r}$ 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. Esses números satisfazem a relação de recorrência
    $\left\{{n \atop k}\right\}_{r}=k\left\{{n-1 \atop k}\right\}_{r}+\left\{{n-1 \atop k-1}\right\}_{r}$
Algumas identidades combinatórias e uma conexão entre esses números e gramáticas livres de contexto podem ser encontradas em.

### 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. É denotado por $S_{r}(n,k)$ e obedece a relação de recorrência
    $S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)$
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 $S^{d}(n,k)$, 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 $|i-j|\geq d$ . Foi demonstrado que estes números satisfazem
    $S^{d}(n,k)=S(n-d+1,k-d+1),n\geq k\geq d$
(daí o nome "reduzido"). Observe (tanto pela definição quanto pela fórmula de redução) que $S^{1}(n,k)=S(n,k)$, os familiares números de Stirling do segundo tipo.