→ 13. Seja a_{n} o número de permutações dos n 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 a_{n}.

Passo 1

O que o enunciado pede e o que temos de dado.
  • Pede-se contar, para cada n\ge1, o número a_{n} de permutações dos inteiros 1,2,\dots,n tal que, em cada permutação, cada elemento (a partir do segundo) difere de 1 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 1.
  • Informação dada: o enunciado define a_n dessa maneira e pede que se construa uma relação de recorrência para a_n e que se resolva essa recorrência (ou seja, encontre a forma fechada de a_n).
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 n é n-1, o único vizinho de 1 é 2, etc.

Passo 2

Intuição com exemplos pequenos (para sentir o problema).
  • Para n=1: só há a permutação (1), então a_1=1.
  • Para n=2: as permutações são (1,2) e (2,1). Em ambas, o segundo elemento difere de 1 do primeiro, então a_2=2.
  • Para n=3: as permutações válidas são (1,2,3), (3,2,1), (2,1,3), (2,3,1) — total 4. Logo a_3=4.
Esses valores sugerem a_n crescendo como potências de 2; 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 [\ell,r] (por exemplo \{3,4,5\}), 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 x. Então o conjunto atual é [x,x].
  • Em cada passo seguinte acrescenta-se ou o número imediatamente menor que \ell (isto é, \ell-1) quando \ell>1, ou o número imediatamente maior que r (isto é, r+1) quando r<n. 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 n-1 (porque partimos do primeiro número e precisamos fazer n-1 acréscimos para chegar a todos os n números).

Passo 4

Contagem para um x inicial fixo — uso de combinatória elementar.
Se o primeiro elemento escolhido for x (com 1\le x\le n), então para alcançar todos os números de 1 a n é necessário, ao longo dos n-1 passos seguintes, fazer exatamente:
  • x-1 escolhas “esquerda” (para pegar x-1,x-2,\dots,1), e
  • n-x escolhas “direita” (para pegar x+1,x+2,\dots,n).
Portanto, para um x fixo a cada permutação válida corresponde uma sequência de n-1 escolhas com exatamente x-1 letras “L” (left) e n-x letras “R” (right). O número de tais sequências é, pela definição de combinação,
\binom{n-1}{x-1},
pois entre as n-1 posições de escolha escolhem-se x-1 posições para os “L” (ou, equivalentemente, n-x posições para os “R”).
Logo, para um dado x \binom{n-1}{x-1} permutações válidas que começam por x.

Passo 5

Somando sobre todos os possíveis inícios x e usar identidade binomial.
Somando sobre x=1,2,\dots,n obtemos
a_n=\sum_{x=1}^{n}\binom{n-1}{x-1}.
Mudando índice (tomando k=x-1, então k vai de 0 a n-1) isso é
a_n=\sum_{k=0}^{n-1}\binom{n-1}{k}.
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 2:
\sum_{k=0}^{n-1}\binom{n-1}{k}=2^{\,n-1}.
Explicação curta desse fato (por completude): é o caso x=1 do Teorema binomial (1+1)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}1^{k}1^{n-1-k}, ou o argumento combinatório de que cada subconjunto de um conjunto com n-1 elementos corresponde a um dos 2^{n-1} padrões de escolha.
Assim obtemos a forma fechada
a_n=2^{\,n-1}.

Passo 6

Construção e resolução da recorrência.
A forma fechada a_n=2^{n-1} satisfaz a recorrência linear simples
a_1=1,\qquad a_n=2\,a_{n-1}\quad\text{para }n\ge2,
porque 2^{n-1}=2\cdot 2^{n-2}. Podemos ver também de forma direta que essa recorrência faz sentido: cada vez que se aumenta n por 1 o número de permutações válidas dobra (interpretação combinatória — na sequência de escolhas “L/R” de comprimento n-1 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 a_1=1 a_n=2^{n-1}: base n=1 ok; supondo a_{n-1}=2^{n-2}, então pela recorrência a_n=2a_{n-1}=2\cdot 2^{n-2}=2^{n-1}. Portanto a solução está consistente.

Resposta

a_1=1,\quad a_n=2\,a_{n-1} para n\ge2
a_n=2^{\,n-1}

Exercícios relacionados