(a) Como visto na Proposição 3.1.7, os Números de Stirling de segunda ordem
são definidos como o número de maneiras de distribuir
bolas numeradas em
urnas indistinguíveis, sem que nenhuma urna fique vazia. Sem utilizar a fórmula obtida na Proposição 3.1.7 ou seja, apresentando um argumento combinatório, mostre que os Números de Stirling de segunda ordem satisfazem a recorrência
Dica: considere
bolas numeradas em
urnas indistinguíveis. Há dois casos, ou a bola
está sozinha em uma urna, ou não está.
(b) Uma permutação dos números
pode ser representada por uma composição de ciclos. Por exemplo, para
, a notação (142)(3)(576) representa a permutação
tal que
e
, o que completa o primeiro ciclo. Depois, temos que
, que é um ciclo de tamanho 1. Por fim,
e
. Os Números de Stirling de primeira ordem sem sinal, geralmente denotados por
, são definidos como o número de permutações de
elementos cuja decomposição em ciclos tem exatamente
ciclos. Por exemplo, a permutação (142)(3)(576) anterior tem três ciclos. Mostre que os Números de Stirling de primeira ordem sem sinal satisfazem à recorrência
Dica: considere uma permutação de
elementos com
ciclos. Há dois casos, ou o
-ésimo elemento está num ciclo de tamanho um, ou não.
Observação. A título de curiosidade, comentamos aqui que os Números de Stirling de primeira ordem com sinal (ou simplesmente Números de Stirling de primeira ordem) são definidos por
. E os nomes de primeira
ordem e de segunda ordem se devem a uma conexão entre estes dois tipos de números, a chamada transformada de Stirling. A transformada de Stirling é a operação que leva uma sequência
na sequência
definida por
onde
são os Números de Stirling de segunda ordem. Curiosamente, a inversa da transformada de Stirling é a operação que leva uma sequência
na sequência
definida por
onde
são os Números de Stirling de primeira ordem (com sinal).
(b) Uma permutação dos números
Observação. A título de curiosidade, comentamos aqui que os Números de Stirling de primeira ordem com sinal (ou simplesmente Números de Stirling de primeira ordem) são definidos por
ordem e de segunda ordem se devem a uma conexão entre estes dois tipos de números, a chamada transformada de Stirling. A transformada de Stirling é a operação que leva uma sequência
Passo 1
Vamos dar uma olhada no que a questão está pedindo. Na parte (a), queremos mostrar que os Números de Stirling de segunda ordem,
, satisfazem a recorrência:
Para isso, vamos usar um argumento combinatório envolvendo a distribuição de
bolas numeradas em
urnas indistinguíveis, garantindo que nenhuma urna fique vazia.
Passo 2
Vamos considerar as duas possibilidades para a última bola, a bola número
:
- A bola
está sozinha em uma urna. - A bola
está compartilhando urna com pelo menos uma outra bola.
Passo 3
Caso 1: Bola
está sozinha em uma urna.
Se a bola
está sozinha, então as outras
bolas devem ser distribuídas nas
urnas restantes (já que uma urna está ocupada pela bola
). O número de maneiras de fazer isso é
.
Passo 4
Caso 2: Bola
não está sozinha.
Se a bola
está compartilhando urna, então ela está sendo colocada em uma das
urnas já existentes que já contêm pelo menos uma bola. Para distribuir as outras
bolas nas
urnas, temos
maneiras. Como a bola
pode ir em qualquer uma das
urnas, multiplicamos por
, ficando
.
Passo 5
Agora, somando os dois casos, obtemos:
Isso confirma a recorrência que queríamos demonstrar.
Passo 6
Agora, vamos para a parte (b) da questão. Queremos mostrar que os Números de Stirling de primeira ordem sem sinal,
, satisfazem a recorrência:
Vamos usar um argumento combinatório baseado na representação das permutações como compostas de ciclos.
Passo 7
Vamos considerar onde o elemento
aparece na permutação:
- O elemento
está em um ciclo de tamanho 1 (isto é, forma um ciclo sozinho). - O elemento
está em um ciclo que contém pelo menos um outro elemento.
Passo 8
Caso 1: Elemento
está em um ciclo de tamanho 1.
Se
forma um ciclo sozinho, então as outras
elementos devem formar
ciclos. O número de maneiras de fazer isso é
.
Passo 9
Caso 2: Elemento
está em um ciclo com outros elementos.
Se
está em um ciclo que inclui pelo menos um outro elemento, podemos pensar em inserir
em qualquer uma das posições disponíveis nos ciclos das permutações de
elementos com
ciclos. Existem
posições onde
pode ser inserido, e o número de permutações é
. Portanto, temos
.
Passo 10
Somando os dois casos, obtemos a recorrência:
Isso conclui a demonstração.
Resposta
Através dos argumentos combinatórios apresentados, mostramos que: