Números de Stirling de segunda espécie

Os números de Stirling de segunda espécie respondem a uma pergunta fundamental de contagem em matemática discreta: dados n objetos distintos, de quantas formas você pode particioná-los em exatamente k grupos não vazios sem rótulo? A resposta se escreve S(n,k) ou às vezes {n choose k} com chaves. Esses números aparecem sempre que você agrupa pessoas em times sem nomear os times, divide um conjunto de chaves em baldes sem rótulo, conta funções sobrejetivas até um fator fatorial, constrói números de Bell como soma sobre k, ou corrige lições que pedem partições de conjuntos em vez de permutações. Esta capacidade aceita inteiros não negativos n (número de itens) e k (número de subconjuntos não vazios) e devolve o S(n,k) exato como string decimal calculada com programação dinâmica BigInt, de modo que valores muito além dos limites de inteiros seguros ordinários permanecem corretos dígito a dígito. Entradas com k negativo ou com k maior que n são rejeitadas com um erro de validação claro em vez de um zero silencioso ou uma resposta errada.

Como se definem os números de Stirling de segunda espécie

Um número de Stirling de segunda espécie S(n,k) conta as partições de um conjunto de n elementos em exatamente k subconjuntos não vazios sem rótulo. A ordem dentro de um subconjunto não importa, e os próprios subconjuntos não são ordenados: a partição {{1,2},{3}} é a mesma que {{3},{1,2}}. A recorrência padrão é S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitivamente, ao adicionar o elemento mais recente n, ou ele forma um singleton próprio (então os n−1 elementos restantes formam k−1 subconjuntos, contados por S(n−1,k−1)), ou ele se junta a um dos k subconjuntos existentes em uma partição dos primeiros n−1 elementos em k blocos (k escolhas, vezes S(n−1,k)). Casos base que fecham a tabela são S(0,0) = 1, S(n,0) = 0 para n > 0, S(0,k) = 0 para k > 0, S(n,1) = 1 e S(n,n) = 1.

Verificações clássicas de livro incluem S(3,2) = 3, S(4,2) = 7, S(5,2) = 15 e S(5,3) = 25. O número de Bell B_n, o total de partições de um n-conjunto com qualquer número de blocos, é a soma de S(n,k) sobre k de zero a n. Objetos relacionados mas diferentes incluem números de Stirling de primeira espécie (que rastreiam permutações por contagem de ciclos) e coeficientes binomiais (que escolhem elementos sem particionar o resto).

Esta implementação nunca usa aproximação de ponto flutuante, amostragem Monte Carlo ou tabelas externas: preenche uma linha de programação dinâmica com aritmética BigInt exata para que cada dígito esteja correto. O caminho é totalmente determinístico — sem sementes aleatórias, relógios, rede nem deriva de modelo — de modo que o mesmo n e k sempre produzem a mesma string.

Onde contagens de Stirling de segunda espécie aparecem no trabalho real

Cursos de combinatória e competições de programação perguntam constantemente de quantas formas dividir n pessoas rotuladas em k times sem rótulo, quantas relações de equivalência em n elementos têm exatamente k classes, ou de quantas formas distribuir n presentes distintos em k caixas idênticas não vazias — tudo o que equivale a S(n,k).

Projetistas de algoritmos usam tabelas de Stirling de segunda espécie ao analisar estruturas de dados de partição de conjuntos, esboços de clustering com número fixo de clusters, ou ao contar as formas como um processo recursivo pode agrupar resultados intermediários. Cursos de probabilidade e estatística conectam S(n,k) ao número de formas de atribuir n resultados distintos a k baldes não vazios sem rótulo e à forma fechada do número de sobrejeções de um n-conjunto sobre um k-conjunto, que é k!

· S(n,k). Educadores e preparação para entrevistas frequentemente mostram um triângulo curto de valores pequenos de S(n,k); calcular uma única entrada em uma chamada mantém demos interativas alinhadas com livros e gabaritos sem manter manualmente tabelas grandes. Se mais tarde precisar de números de Stirling de primeira espécie, apenas números de Bell, contagens de sobrejeção com o fator k! já aplicado, ou uma listagem explícita de partições em vez da contagem, trate-os como intenções de busca separadas em vez de sobrecarregar esta página.