Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência

Passo 1

Beleza, vamos lá! O enunciado pede para deduzirmos uma equação de recorrência para , que são as permutações caóticas ou derangements de um conjunto com elementos. Isso está no campo da Combinatória, mais especificamente em Permutações sem Fixos. Para resolver isso, vamos precisar entender como contar as permutações onde nenhum elemento fica na posição original.

Passo 2

Primeiro, vamos pensar em como formar uma permutação caótica de elementos. Vamos escolher um elemento específico, digamos o número 1, e ver para onde ele pode ir. Como estamos falando de permutações sem fixos, o 1 não pode ficar na primeira posição. Então, ele tem posições possíveis para ir.

Passo 3

Suponha que o 1 vá para a posição (onde ). Agora temos duas possibilidades:
  1. O elemento que estava na posição vai para a posição 1.
  2. O elemento que estava na posição não vai para a posição 1.

Passo 4

Caso 1: Se o elemento na posição vai para a posição 1, então estamos basicamente trocando esses dois elementos. Agora, o restante dos elementos precisa ser uma permuta��ão caótica de si mesmos. Ou seja, há maneiras de fazer isso.
Caso 2: Se o elemento na posição não vai para a posição 1, então ele deve ir para outra posição diferente de . Nesse caso, os elementos restantes (excluindo o 1 que já foi colocado) precisam formar uma permutação caótica. Portanto, há maneiras de fazer isso.

Passo 5

Como o elemento 1 tem opções para escolher onde vai, e para cada uma dessas escolhas temos possibilidades (dos casos 1 e 2), a equação de recorrência fica:

Resposta

A equação de recorrência deduzida é:

Exercícios relacionados

Encontre uma recorrência para , o número de sequências de letras dentre ou , que não têm letras vizinhas.
Considere o conjunto das sequências de tamanho tais que cada entrada pertence a e entradas vizinhas sempre diferem por 1 em módulo. Descreva um sistema de equações de recorrência para resolver este problema.
Uma triangulação de um polígono convexo é uma divisão de em triângulos usando algumas de suas diagonais de modo que suas diagonais não se intersectem, veja a Figura 3.10. Encontre uma relação de recorrência
Figura 3.10. Duas triangulações diferentes do pentágono .
para , onde denota o número de triangulações de um polígono convexo de lados.
Dica: para ajudar na contagem, fixe um lado do polígono e o triângulo que contém esse lado, e faça a contagem. Depois some sobre todos os triângulos possíveis que contém esse lado.
Considere um reticulado . Vamos chamar de trajetória permitida um caminho poligonal que sai de , chega em , nunca toca pontos abaixo da diagonal e a cada passo sobe uma unidade ou anda para a direita uma unidade, veja a Figura 3.11. Seja o número de trajetórias permitidas. Determine uma relação de recorrência para .
Figura 3.11. Exemplo de trajetória permitida.