→ 13. Seja
o número de permutações dos
primeiros números naturais tais que cada elemento difere de uma unidade de algum elemento à sua esquerda na permutação. Construa e resolva uma relação de recorrência para
.
Passo 1
O que o enunciado pede e o que temos de dado.
- Pede-se contar, para cada
, o número de permutações dos inteiros tal que, em cada permutação, cada elemento (a partir do segundo) difere de de algum elemento que aparece à sua esquerda. Em outras palavras: para cada posição da permutação (exceto a primeira), o valor colocado nessa posição tem que ser igual a algum valor já colocado antes mais ou menos . - Informação dada: o enunciado define
dessa maneira e pede que se construa uma relação de recorrência para e que se resolva essa recorrência (ou seja, encontre a forma fechada de ).
Observação importante (só para garantir que está claro): a condição significa que, quando lemos a permutação da esquerda para a direita, cada novo número que aparece deve ser um vizinho (em valor) de algum número já visto — e o único vizinho de
é
, o único vizinho de
é
, etc.
Passo 2
Intuição com exemplos pequenos (para sentir o problema).
- Para
: só há a permutação , então . - Para
: as permutações são e . Em ambas, o segundo elemento difere de do primeiro, então . - Para
: as permutações válidas são , , , — total . Logo .
Esses valores sugerem
crescendo como potências de
; vamos provar isso rigorosamente e obter uma recorrência.
Passo 3
Descrição do processo construtivo (estratégia que vamos usar).
Pense em construir uma permutação válida colocando os números um a um da esquerda para a direita. Depois de colocar alguns números, o conjunto dos números já colocados é sempre um intervalo contíguo
(por exemplo
), porque a regra só permite acrescentar números que sejam vizinhos, então o conjunto nunca separa em duas componentes distantes.
- Começa-se escolhendo o primeiro elemento
. Então o conjunto atual é . - Em cada passo seguinte acrescenta-se ou o número imediatamente menor que
(isto é, ) quando , ou o número imediatamente maior que (isto é, ) quando . Ou seja, em cada passo válido escolhe-se expandir o intervalo para a esquerda ou para a direita, enquanto esses números existirem.
Essa visão transforma cada permutação válida numa sequência de escolhas “esquerda/ direita” de comprimento
(porque partimos do primeiro número e precisamos fazer
acréscimos para chegar a todos os
números).
Passo 4
Contagem para um
inicial fixo — uso de combinatória elementar.
Se o primeiro elemento escolhido for
(com
), então para alcançar todos os números de
a
é necessário, ao longo dos
passos seguintes, fazer exatamente:
-
escolhas “esquerda” (para pegar ), e -
escolhas “direita” (para pegar ).
Portanto, para um
fixo a cada permutação válida corresponde uma sequência de
escolhas com exatamente
letras “L” (left) e
letras “R” (right). O número de tais sequências é, pela definição de combinação,
pois entre as
posições de escolha escolhem-se
posições para os “L” (ou, equivalentemente,
posições para os “R”).
Logo, para um dado
há
permutações válidas que começam por
.
Passo 5
Somando sobre todos os possíveis inícios
e usar identidade binomial.
Somando sobre
obtemos
Mudando índice (tomando
, então
vai de
a
) isso é
Aqui entra a identidade básica do binômio: a soma de todos os coeficientes binomiais numa linha de Pascal vale uma potência de
:
Explicação curta desse fato (por completude): é o caso
do Teorema binomial
, ou o argumento combinatório de que cada subconjunto de um conjunto com
elementos corresponde a um dos
padrões de escolha.
Assim obtemos a forma fechada
Passo 6
Construção e resolução da recorrência.
A forma fechada
satisfaz a recorrência linear simples
porque
. Podemos ver também de forma direta que essa recorrência faz sentido: cada vez que se aumenta
por
o número de permutações válidas dobra (interpretação combinatória — na sequência de escolhas “L/R” de comprimento
acrescenta-se uma última escolha que pode ser L ou R em termos do processo visto; tecnicamente é consequência da soma binomial acima).
Passo 7
Verificação por indução (breve) — garantia de coerência.
Para fechar com segurança, pode-se checar por indução que a recorrência com
dá
: base
ok; supondo
, então pela recorrência
. Portanto a solução está consistente.