- De quantas maneiras distintas podemos colocar cartas em envelopes endereçados a destinatários diferentes, de modo que nenhuma das cartas seja colocada no envelope correto?
Relatos históricos indicam que esse problema foi originalmente proposto por Nicolaus Bernoulli, membro da prestigiosa família Bernoulli, no séc XVIII, e resolvido pelo célebre matemático Leonhard Euler.
Esse problema ilustra uma daquelas situações nas quais nos perguntamos:
– E se der tudo errado? E se nada ocorrer conforme prevíamos?
Em Análise Combinatória, situações como essas são estudadas utilizando o que a matemática denomina como Permutação Caótica.
Aqui, vamos explorar um pouco da matemática desse assunto que apresentamos de uma maneira informal na Sala Inicial.
O que você precisa saber
Para que você entenda sem problemas o que iremos apresentar, você vai precisar de dois objetos e um princípio da matemática. Vamos fazer uma brevíssima apresentação dos três assuntos e deixaremos indicadas Salas do nosso Blog nas quais você encontrará material que pode ajudá-lo, caso você queira ou precise aprofundar seu conhecimento.
Para acessar as informações de um dos quatro tema, clique no botão correspondente.
Chamamos de fatorial de [tex]n[/tex], e denotamos por [tex]n![/tex], ao produto dos números naturais consecutivos de [tex]1[/tex] até [tex]n[/tex].
Assim:
[tex]\qquad n!=1 \cdot 2 \cdot 3 \cdot \dots \cdot(n-1) \cdot n\,.[/tex]
Note, então, que o fatorial de [tex]n[/tex] é calculado pela multiplicação de [tex]n[/tex] por todos os seus antecessores, até chegar ao número [tex]1[/tex].
A definição de fatorial é estendida para todos os números naturais, definindo-se [tex]0!=1[/tex] e [tex]1!=1.[/tex]
Dessa forma, se [tex]n[/tex] é um número natural qualquer, então:
[tex]\qquad n!=\begin{cases}
1,\text{ se } n=0; \\ 1, \text{ se } n=1; \\1 \cdot 2 \cdot \dots \cdot n, \text{ se } n\gt 1. \end{cases}[/tex]
Vamos conferir alguns exemplos? Observe:
[tex]\qquad 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24[/tex];
[tex]\qquad 6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720[/tex];
[tex]\qquad 8! = 8 \cdot 7 \cdot 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40320[/tex];
[tex]\qquad 10! = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 3628800[/tex];
[tex]\qquad 13! = 13\cdot 12 \cdot 11 \cdot \cdots \cdot \cdot 3 \cdot 2 \cdot 1 = 6227020800[/tex].
Uma propriedade dos fatoriais que utilizaremos com frequência é esta:
- Se [tex]a[/tex] e [tex]b[/tex] são números naturais, com [tex]a\gt b[/tex], então:
[tex] \qquad\qquad \dfrac{a!}{b!} = a(a-1)(a-2)\cdot\, \dots\, \cdot(b+1)[/tex]
ou, de forma equivalente,
[tex]\qquad\qquad a!=a(a-1)(a-2)\cdot\, \dots\, \cdot(b+1)\cdot b! [/tex].
Se você precisar de mais informações sobre fatorial, visite esta Sala do nosso Blog.
O Princípio Multiplicativo, ou Princípio Fundamental da Contagem, ou simplesmente PFC, é a principal técnica para resolução de problemas de contagem. Ele assegura que:
Se
- uma decisão D1 puder ser tomada de [tex] m_1 [/tex] maneiras distintas,
- uma decisão D2 puder ser tomada de [tex] m_2 [/tex] maneiras distintas,
- [tex]\cdots[/tex]
- uma decisão Dk puder ser tomada de [tex]m_k [/tex] maneiras distintas e
- todas essas decisões forem independentes entre si (isto é, a escolha de uma não muda a quantidade de possibilidades para a escolha de outra),
então o número total de maneiras de tomarmos sucessivamente essas [tex]k[/tex] decisões é igual ao produto
[tex]\qquad \qquad \boxed{m_1\times m_2 \times \cdots \times m_k} \, .[/tex]
Se você precisar de mais informações sobre este Princípio, visite esta Sala do nosso Blog.
Agora, se você quiser se descontrair com o PFC, assista a este vídeo. Só não se esqueça de fechar a janelinha depois quem o vídeo terminar.
Uma permutação de [tex]n[/tex] objetos é uma sequência ordenada desses [tex]n[/tex] objetos, onde cada um deles aparece uma única vez.
Em problemas de combinatória, costuma-se chamar de, Permutações simples são definidas como maneiras de organizarmos [tex]n[/tex] objetos distintos em uma fila. O número total de permutações simples é denotado por [tex]P_n[/tex] e, segue do princípio multiplicativo, que [tex]\boxed{P_n=n!}\,.[/tex]
Vejamos:
- O número de maneiras que podemos escolher o objeto que ocupará o primeiro lugar da fila é [tex]n[/tex].
- Escolhido o primeiro elemento, o número de maneiras que podemos escolher o objeto que ocupará o segundo lugar da fila é [tex]n-1[/tex].
- Escolhidos o primeiro e o segundo elementos, o número de maneiras que podemos escolher o objeto que ocupará o terceiro lugar da fila é [tex]n-2[/tex].
- Escolhidos o primeiro, o segundo e o terceiro elementos, o número de maneiras que podemos escolher o objeto que ocupará o quarto lugar da fila é [tex]n-3[/tex].
- Seguimos com esse raciocínio, até esgotar as [tex]n[/tex] posições da fila.
| [tex]n[/tex] escolhas | [tex](n-1)[/tex] escolhas | . . . | [tex]2[/tex] escolhas | [tex]1[/tex] escolha | ||||
| 1º lugar da fila | 2º lugar da fila | (n-1)º lugar da fila | nº lugar da fila |
O Princípio Multiplicativo nos assegura que essas [tex]n[/tex] escolhas são feitas simultaneamente de [tex]n![/tex] maneiras distintas.
Se você precisar de mais informações sobre Permutações Simples, visite esta Sala do nosso Blog.
Uma das maneiras de agruparmos elementos de um dado conjunto é escolhê-los levando-se em consideração apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos é denominado uma Combinação simples. Especificamente, quando escolhemos [tex]r[/tex] dentre [tex]n[/tex] elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combinação simples de [tex]n[/tex] elementos tomados [tex]r[/tex] a [tex]r[/tex].
E o legal é que, dado um conjunto finito, podemos determinar quantos agrupamentos desse tipo podemos fazer, sem que precisemos exibi-los.
- O número de Combinações simples de [tex]n[/tex] elementos, tomados [tex]r[/tex] a [tex]r[/tex], é denotado por [tex]C_{n\, ,\, r}[/tex] ou [tex]C_n^r[/tex] e assim definido:
[tex]C_{n\, ,\, r}=C_n^r=\dfrac{n!}{(n-r)!\, r!} \text{, com } n,r \in\mathbb{N} \text{ e }\, r\leqslant n[/tex].
O quociente [tex]\dfrac{n!}{(n-r)!\, r!}[/tex] também pode ser denotado por [tex]\dbinom{n}{r}[/tex] e nesse caso é denominado coeficiente binomial ou número binomial.
Se você precisar de mais informações sobre Combinações Simples, assista a este vídeo. Só não se esqueça de fechar a janelinha depois que ele terminar.
Permutações caóticas
Uma permutação dos elementos dessa sequência é dita uma Permutação Caótica ou um Desarranjo quando nenhum dos elementos [tex]a_i[/tex] está na sua posição original, isto é, na [tex]i[/tex]-ésima posição.
Denotaremos por [tex]D_{n}[/tex] o número de permutações caóticas de [tex]n[/tex] elementos.
Observe que o conceito de Permutação Caótica é relativo a uma disposição inicial que tomamos como referencial ou padrão. Além disso, o número [tex]D_{n}[/tex] não está associado ao tipo de elementos de uma sequência, mas sim às posições ocupadas por tais elementos. Dessa forma, é comum em alguns livros sobre o assunto que a definição de Permutação Caótica de [tex]n[/tex] elementos se refira à sequência [tex](1,\, 2,\, 3,\, \cdots\, ,n).[/tex]
A nossa discussão inicial será sobre uma justificativa da fórmula para o número de permutações caóticas [tex]D_{n}[/tex] apresentada na Sala inicial :
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=n! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dots + \dfrac{(-1)^{n}}{n!}\right]$}\, [/tex].
Para acompanhar a discussão, basta clicar no próximo botão.
- [tex]\textcolor{#629D90}{C}[/tex] o conjunto de todas as permutações dos elementos de [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex];
- [tex]\textcolor{#629D90}{C_1}[/tex] o conjunto das permutações de [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex] nas quais o elemento [tex]a_1[/tex] ocupa o primeiro lugar na sequência;
- [tex]\textcolor{#629D90}{C_2}[/tex] o conjunto das permutações dos elementos de [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex] nas quais o elemento [tex]a_2[/tex] ocupa o segundo lugar na sequência;
- [tex]\textcolor{#629D90}{C_i}[/tex] o conjunto das permutações dos elementos de [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex] nas quais o elemento genérico [tex]a_i[/tex] ocupa o lugar [tex]i[/tex] na sequência,
e por [tex]c, c_1, c_2, \cdots, c_n[/tex] o número de elementos dos conjuntos [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex], respectivamente.
Observe que
► [tex]D_n[/tex] será o número de sequências de [tex]C[/tex] que pertencem a exatamente ZERO dos conjuntos [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex];
assim, do total [tex]c[/tex] de todas as permutações de [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex], devemos subtrair as sequências que pertencem a, pelo menos, um dos conjuntos [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex].
Vamos lá!
[tex]\textcolor{#589386}{(1)}[/tex] Como as sequências que queremos não podem ter elementos nas suas posições originais, essas sequências não podem pertencer aos conjuntos [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex]. Portanto, devemos inicialmente subtrair de [tex]c[/tex] o número de elementos desses conjuntos. Considere, então a seguinte diferença:
[tex]\qquad X_1=c-c_1-c_2-\cdots-c_n [/tex].
Veja que em cada conjunto [tex]\textcolor{#629D90}{C_i}[/tex], fixamos apenas o elemento [tex]a_i[/tex] na posição [tex]i[/tex]; as demais [tex]n-1[/tex] posições podem ser ocupadas por quaisquer dos elementos restantes da sequência original. Com isso, temos que cada [tex]c_i[/tex] é o número de permutações de [tex]n-1[/tex] elementos, ou seja,
[tex]\qquad c_1=c_2=\cdots=c_n=P_{n-1}=\left(n-1\right)!\,[/tex].
Portanto, seque que:
[tex]\qquad X_1=c-c_1-c_2-\cdots-c_n =c-\left(c_1+c_2+\cdots+c_n\right)\\
\qquad X_1=c-\left[\underbrace{\left(n-1\right)!+\left(n-1\right)!+\cdots+\left(n-1\right)!}_{n \text{ vezes }}\right]\\
\qquad X_1=c-n\cdot\left(n-1\right)![/tex].
Terminamos? [tex]D_n=X_1[/tex]?
Não!
[tex]\textcolor{#589386}{(2)}[/tex] Observe que várias sequências de [tex]\textcolor{#629D90}{C}[/tex] foram subtraídas mais de uma vez. Com efeito, sequências do tipo [tex]\left(\,\underline{\quad}\,,\textcolor{red}{a_2},\textcolor{red}{a_3},\,\underline{\quad}\,\cdots,\,\underline{\quad}\ \right)[/tex], por exemplo, foram retiradas da nossa contagem pelo menos duas vezes: como elementos de [tex]\textcolor{red}{C_2}[/tex] e como elementos de [tex]\textcolor{red}{C_3}[/tex]. Assim, precisamos acrescentar na nossa contagem o número de sequências que estão nas interseções do tipo [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}[/tex], para [tex]i\ne j[/tex]. E que número é esse?
Fixados [tex]i\, [/tex] e [tex]\, j[/tex], com [tex]1\leqslant i\lt j\leqslant n[/tex], as sequências que estão em [tex]\textcolor{red}{C_i}[/tex] e em [tex]\textcolor{red}{C_j}[/tex] têm duas posições fixas, a [tex]i[/tex]-ésima e [tex]j[/tex]-ésima posições, e as [tex]n-2[/tex] demais são livres. Temos então [tex]P_{n-2}=\left(n-2\right)![/tex] sequências em cada interseção [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}[/tex].
Mas quantas dessas interseções nós temos? Como [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}= \textcolor{#629D90}{C_j} \cap \textcolor{#629D90}{C_i}[/tex], a quantidade de interseções é o número de Combinações Simples de [tex]n[/tex] elementos tomados [tex]2[/tex] a [tex]2[/tex]: [tex]C_{n\, ,\, 2}=\dfrac{n!}{(n-2)!\, 2!}[/tex].
Assim, devemos acrescentar à nossa contagem [tex]\dfrac{n!}{(n-2)!\, 2!}\cdot (n-2)! =\dfrac{n!}{2!}[/tex] sequências que foram indevidamente retiradas. Obtemos então uma segunda contagem parcial das permutações caóticas:
[tex]\qquad X_2=X_1+\dfrac{n!}{2!}\\
\qquad X_2=c-n!+\dfrac{n!}{2!}[/tex].
Terminamos? [tex]D_n=X_2[/tex]?
De novo, Não!
[tex]\textcolor{#589386}{(3)}[/tex] Observe que, agora, várias sequências foram acrescentadas a mais …
Com efeito, sequências do tipo [tex]\left(\,\underline{\quad}\,,\textcolor{red}{a_2},\textcolor{red}{a_3},\textcolor{red}{a_4},\,\underline{\quad}\,\cdots,\,\underline{\quad}\ \right)[/tex], por exemplo, foram contadas na nossa contagem pelo menos três vezes: como elementos de [tex]\textcolor{red}{C_2}\cap \textcolor{red}{C_3}[/tex], como como elementos de [tex]\textcolor{red}{C_2}\cap \textcolor{red}{C_4}[/tex] e como elementos de [tex]\textcolor{red}{C_3}\cap \textcolor{red}{C_4}[/tex]. Poxa, agora vamos precisar tirar da nossa contagem o número de sequências que estão nas interseções do tipo [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}\cap \textcolor{#629D90}{C_k}[/tex], para [tex]i\ne j\lt k[/tex]. E que número é esse?
Fixados [tex]i\, [/tex], [tex]\, j[/tex] e [tex]\, k[/tex], com [tex]1\leqslant i\lt j\lt k \leqslant n[/tex], as sequências que estão em [tex]\textcolor{red}{C_i}[/tex], em [tex]\textcolor{red}{C_j}[/tex] e em [tex]\textcolor{red}{C_k}[/tex] têm três posições fixas, a [tex]i[/tex]-ésima, [tex]j[/tex]-ésima e [tex]k[/tex]-ésima posições, e as [tex]n-3[/tex] demais são livres. Temos então [tex]P_{n-3}=\left(n-3\right)![/tex] sequências em cada interseção [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}\cap \textcolor{#629D90}{C_k}[/tex].
Quantas dessas interseções temos? Como [tex]\textcolor{#629D90}{C_i} \cap \textcolor{#629D90}{C_j}\cap \textcolor{#629D90}{C_k}[/tex] independe da ordem dos três conjuntos, a quantidade de interseções é o número de Combinações Simples de [tex]n[/tex] elementos tomados [tex]3[/tex] a [tex]3[/tex]: [tex]C_{n\, ,\, 3}=\dfrac{n!}{(n-3)!\, 3!}[/tex].
Vamos, então, subtrair da nossa contagem [tex]\dfrac{n!}{(n-3)!\, 3!}\cdot (n-3)! =\dfrac{n!}{3!}[/tex] sequências que foram indevidamente acrescentadas. Obtemos então uma terceira contagem parcial das permutações caóticas:
[tex]\qquad X_3=X_2-\dfrac{n!}{3!}\\
\qquad X_3=c-n!+\dfrac{n!}{2!}-\dfrac{n!}{3!}[/tex].
Agora terminamos? [tex]D_n=X_3[/tex]?
Bom,aí vai depender…
[tex]\textcolor{#589386}{(4)}[/tex] Se tivermos interseções de quatro conjuntos distintos dentre [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex], então retiramos da nossa última contagem parcial mais sequências do que devíamos. Essas sequências deverão ser recontadas e acrescentaremos [tex]\dfrac{n!}{4!}[/tex] sequências à nossa última contagem, obtendo:
[tex]\qquad X_4=X_3+\dfrac{n!}{4!}\\
\qquad X_4=c-n!+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\dfrac{n!}{4!}.[/tex]
E prosseguimos com contagens parciais
[tex] \qquad X_k=c-n!+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\dfrac{n!}{4!}+ \cdots +\left(-1\right)^k\dfrac{n!}{k!} [/tex],
até considerarmos a maior interseção possível de conjuntos distintos dentre [tex]\textcolor{#629D90}{C_1}, \textcolor{#629D90}{C_2}, \textcolor{#629D90}{C_3}, \cdots , \textcolor{#629D90}{C_n}[/tex] que é a interseção [tex]\textcolor{#629D90}{C_1} \cap \textcolor{#629D90}{C_2} \cap \textcolor{#629D90}{C_3} \cap \cdots \cap \textcolor{#629D90}{C_n}[/tex], da qual faz parte apenas a sequência original [tex]\left(a_1,\,a_2,\,\cdots \, , \, a_n \right) [/tex].
Pelo exposto, temos que:
[tex]\qquad D_n=c-n!+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\dfrac{n!}{4!}+ \cdots +\left(-1\right)^k\dfrac{n!}{k!} + \cdots +\left(-1\right)^n\dfrac{n!}{n!} [/tex]
e, como [tex]c[/tex] é o número de permutações dos [tex]n[/tex] elementos [tex]a_1,a_2,a_3,\cdots,a_n[/tex] que formam as sequências, segue que:
[tex]\qquad D_n=n!-n!+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\dfrac{n!}{4!}+ \cdots +\left(-1\right)^n\dfrac{n!}{n!} [/tex].
Mas [tex]0!=1\, [/tex] e [tex]\, 1!=1\, [/tex]; portanto, finalmente podemos concluir que:
[tex]\qquad D_n=\dfrac{n!}{0!}-\dfrac{n!}{1!}+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\dfrac{n!}{4!}+ \cdots +\left(-1\right)^n\dfrac{n!}{n!} [/tex]
[tex]\qquad \fcolorbox{black}{#B2EDE0}{$D_{n}=n! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dots + \dfrac{(-1)^{n}}{n!}\right]$}\, [/tex].
Continuando a nossa discussão, vamos aproveitar a ideia utilizada na discussão informal que antecedeu a apresentação da fórmula de recorrência
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)$}\,[/tex].
na Sala inicial para fazer uma justificativa mais completa dessa fórmula de recorrência.
Para acompanhar mais esta discussão, basta clicar no próximo botão.
Vamos considerar mais uma vez a sequência ordenada [tex]\left(a_1, a_2, a_3, \cdots , a_n\right)[/tex] e denotar por [tex]D_n[/tex] o número de permutações caóticas, isto é, a quantidade de permutações dos [tex]n[/tex] elementos [tex]a_1, a_2, a_3, \cdots , a_n[/tex] nas quais nenhum deles ocupa sua posição original na sequência inicial. Observe que:
- Quando [tex]n = 1[/tex], temos somente um elemento na sequência, [tex]\left(a_1\right)[/tex]. Logo não existe forma de "desarranjar" a sequência e, portanto, [tex]D_1=0\,.[/tex]
- Quando [tex]n = 2[/tex], temos somente a sequência, [tex]\left(a_1,a_2\right)[/tex]. Veja que podemos "desarranjar" a sequência apenas de uma forma: [tex]\left(a_2,a_1\right)[/tex]; portanto, [tex]D_2=1\,.[/tex]
- Já sabemos que é inviável continuar fazendo discussões para valores particulares de [tex]n[/tex], pois rapidamente atingiremos valores para os quais nos perderemos em continhas e mais continhas. Assim, vamos trabalhar com a sequência genérica inicial [tex]\left(a_1, a_2, a_3, \cdots , a_n\right)[/tex], com [tex]n\gt 2.[/tex]
- A segunda posição é ocupada por [tex]a_1[/tex]:
- A segunda posição NÃO é ocupada por [tex]a_1[/tex]:
Rearranjando os elementos dessa sequência de modo que nenhum fique na posição original, existem [tex] n-1[/tex] opções para o primeiro elemento, já que ele não pode ser [tex]a_1[/tex]. Temos então sequências da forma:
[tex]\qquad \qquad (\textcolor{red}{a_2},\underbrace{\underline{\quad}\,,\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}})[/tex] ; [tex](\textcolor{red}{a_3},\underbrace{\underline{\quad}\,,\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}})[/tex] ; [tex](\textcolor{red}{a_4},\underbrace{\underline{\quad}\,,\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}})[/tex] ; … ; [tex](\textcolor{red}{a_n},\underbrace{\underline{\quad}\,,\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}})\,.[/tex]
Fixada uma dessas [tex]n-1[/tex] formas de ordenamento, vamos determinar quantas sequências caóticas essa forma define. Para isso vamos analisar o comportamento dos elementos que estão posicionados da segunda posição em diante. Assim, para [tex]1 \lt k \leqslant n[/tex], considere a sequência [tex](\textcolor{red}{a_k},\underbrace{\underline{\quad}\,,\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}\;\,})[/tex]. Vamos contar as formas de rearranjarmos os [tex]n-1[/tex] últimos elementos, de forma que eles não voltem para suas posições originais.
Observe que podemos ter duas situações: a segunda posição é ocupada por [tex]a_1[/tex] e a segunda posição não é ocupada por [tex]a_1[/tex]. Vamos analisar as duas situações separadamente:
Neste caso, temos a sequência
[tex]\qquad \qquad \quad (\textcolor{red}{a_k},\textcolor{blue}{a_1}\,,\underbrace{\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-2)\text{ elementos}\,\;})[/tex]
e precisamos contar de quantas maneiras podemos rearranjar os [tex]n-2[/tex] elementos restantes de modo que nenhum volte à sua posição de origem.
Isso equivale a contar quantas permutações caóticas com [tex]n-2[/tex] elementos existem:[tex]\,\, (\underbrace{\,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-2)\text{ elementos}\,\;})\,.[/tex]
Numericamente não sabemos quantas são, mas essa quantidade é denotada por [tex]\boxed{D_{n-2}}\,.[/tex]
Neste caso, temos uma sequência da forma
[tex]\qquad \qquad \quad (\textcolor{red}{a_k},\underbrace{\,\underline{\textcolor{blue}{\ne a_1}}\,,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}\,\;})[/tex]
e precisamos contar de quantas maneiras podemos rearranjar os [tex]n-1[/tex] elementos restantes de modo que nenhum volte à sua posição de origem.
Isso equivale a contar quantas permutações caóticas com [tex]n-1[/tex] elementos existem:[tex]\,\, (\underbrace{\,\underline{\quad}\,,\underline{\quad}\,, \cdots ,\,\underline{\quad}\,\,}_{ (n-1)\text{ elementos}\,\;})\,.[/tex]
Numericamente não sabemos quantas são, mas essa quantidade é denotada por [tex]\boxed{D_{n-1}}\,.[/tex]
Como os rearranjos das duas alternativas formam conjuntos disjuntos, temos que quando [tex]a_k[/tex] ocupa a primeira posição, existem [tex]\boxed{D_{n−1}+D_{n−2}}[/tex] permutações caóticas possíveis.
Por outro lado, existem [tex]n-1[/tex] opções de elementos para a primeira posição; assim, pelo Princípio Multiplicativo, temos que:
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)$}\,,\, \forall n \in \mathbb{N}, \, n \gt 2[/tex].
Obtemos assim, uma fórmula de recorrência que resolve vários problemas, mas tem o inconveniente de não fornecer [tex]D_n[/tex] como uma função explícita do número [tex]n\,.[/tex]
Este vídeo mostra a solução genérica do problema da prateleira com livros apresentado na Sala inicial .
O raciocínio utilizado é bem parecido com a demonstração que fizemos para a fórmula de recorrência das Permutações Caóticas.
Livros na prateleira
Para que você não pense que as duas fórmulas que apresentamos não estão relacionadas ou não forneçam os mesmos valores, vamos obter a primeira como consequência da segunda.
Acompanhe a dedução clicando no botão abaixo.
A segunda dedução que fizemos nos mostra que, para qualquer número natural [tex]n[/tex], com [tex]n \gt 2[/tex],
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)$}\,. \qquad \textcolor{#800000}{(i)}[/tex].
Observe que se fizermos [tex]n=3[/tex] em [tex]\textcolor{#800000}{(i)}[/tex], temos que [tex]D_{3}=2\cdot \left(D_{1}+D_{2}\right)[/tex]. Assim, somando [tex]\textcolor{red}{-3D_2}[/tex] em ambos os lados dessa igualdade, segue que:
[tex]\qquad D_{3}-\textcolor{red}{3D_2}=2\cdot \left(D_{1}+D_{2}\right)-\textcolor{red}{3D_2}[/tex]
[tex]\qquad D_{3}-3D_2=2D_{1}+2D_{2}-3D_2[/tex]
[tex]\qquad D_{3}-3D_2=2D_{1}-D_2[/tex]
[tex]\qquad D_{3}-3D_2=-\left(D_2-2D_{1}\right)[/tex]
Analogamente, [tex]n=4[/tex] e [tex]n=5[/tex] em [tex]\textcolor{#800000}{(i)}[/tex] e somando, respectivamente, [tex]\textcolor{blue}{-4D_3}[/tex] e [tex]\textcolor{#449C00}{-5D_4}[/tex] em ambos os lados das igualdades obtidas, segue que:
|
[tex]\quad D_{4}=3\cdot \left(D_{2}+D_{3}\right)[/tex] [tex]\quad D_{4}-\textcolor{blue}{4D_3}=3\cdot \left(D_{2}+D_{3}\right)-\textcolor{blue}{4D_3}[/tex] [tex]\quad D_{4}-4D_3=3D_{2}+3D_{3}-4D_3[/tex] [tex]\quad D_{4}-4D_3=3D_{2}-D_3[/tex] [tex]\quad D_{4}-4D_3=-\left(D_3-3D_{2}\right)[/tex] |
[tex]\quad D_{5}=4\cdot \left(D_{3}+D_{4}\right)[/tex] [tex]\quad D_{5}-\textcolor{#449C00}{5D_4}=4\cdot \left(D_{3}+D_{4}\right)-\textcolor{#449C00}{5D_4}[/tex] [tex]\quad D_{5}-5D_4=4D_{3}+4D_{4}-5D_4[/tex] [tex]\quad D_{5}-5D_4=4D_{3}-D_4[/tex] [tex]\quad D_{5}-5D_4=-\left(D_4-4D_{3}\right)[/tex] |
Dessa forma, para qualquer número natural [tex]n[/tex], com [tex]n \gt 2[/tex], temos que:
[tex]\qquad D_{3}-3D_2=-\left(D_2-2D_{1}\right)[/tex]
[tex]\qquad D_{4}-4D_3=-\left(D_3-3D_{2}\right)[/tex]
[tex]\qquad D_{5}-5D_4=-\left(D_4-4D_{3}\right)[/tex]
[tex]\qquad \qquad \vdots[/tex]
[tex]\qquad D_{n}-nD_{n-1}=-\left(D_{n-1}-(n-1)D_{n-2}\right).[/tex]
Multiplicando essas [tex]n-2[/tex] igualdades, obtemos:
[tex]\left(D_{3}-3D_2\right)\cdot \left(D_{4}-4D_3\right)\cdot \left( D_{5}-5D_4\right)\cdot \ldots \cdot \left(D_{n}-nD_{n-1}\right)=\\
=\left(-1\right)^{n-2}\cdot \left(D_2-2D_{1}\right) \cdot \left(D_3-3D_{2}\right) \cdot \left(D_4-4D_{3}\right)\cdot \ldots \cdot\left(D_{n-1}-(n-1)D_{n-2}\right).[/tex]
Veja quantos cancelamentos podemos fazer, já que temos produtos dos dois lados da igualdade:
[tex]\;\cancel{\left(D_{3}-3D_2\right)}\cdot \cancel{\left(D_{4}-4D_3\right)}\cdot \cancel{\left( D_{5}-5D_4\right)}\cdot \ldots \cdot \left(D_{n}-nD_{n-1}\right)=\\
\;=\left(-1\right)^{n-2}\cdot \left(D_2-2D_{1}\right) \cdot \cancel{ \left(D_3-3D_{2}\right)} \cdot \cancel{\left(D_4-4D_{3}\right)}\cdot \ldots \cdot \cancel{\left(D_{n-1}-(n-1)D_{n-2}\right)}.[/tex]
Depois dos cancelamentos, ficamos com uma igualdade bastante reduzida:
[tex]\qquad D_{n}-nD_{n-1}=\left(-1\right)^{n-2}\cdot \left(D_2-2D_{1}\right). \qquad \textcolor{#800000}{(ii)}[/tex]
Agora, observe que:
- [tex]\left(-1\right)^{n-2}=\left(-1\right)^{n}[/tex].
- [tex]D_2-2D_{1}=1-2\cdot 0=1\,[/tex],
assim, podemos reescrever a igualdade [tex]\textcolor{#800000}{(ii)}[/tex]:
[tex]\qquad D_{n}-nD_{n-1}=\left(-1\right)^{n}\cdot 1[/tex]
[tex]\qquad D_{n}-nD_{n-1}=\left(-1\right)^{n}[/tex]
[tex]\qquad D_{n}=\left(-1\right)^{n}+nD_{n-1}, \forall\,n\gt 2. \qquad \textcolor{#800000}{(iii)}[/tex]
Dividindo a a igualdade [tex]\textcolor{#800000}{(iii)}[/tex] por [tex]n![/tex], vem que:
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {\left(-1\right)^{n}}{n!}+\dfrac {nD_{n-1}}{n!}[/tex]
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {\left(-1\right)^{n}}{n!}+\dfrac {D_{n-1}}{(n-1)!}, \forall\,n\gt 2. \qquad \textcolor{#800000}{(iv)}[/tex]
Perceba que, como [tex]D_2=1[/tex] e [tex]D_1=0[/tex] , temos que:
[tex]\qquad \dfrac {\left(-1\right)^{2}}{2!}+\dfrac {D_{1}}{1!}=\dfrac{1}{2}+\dfrac{0}{1}=\dfrac{D_2}{2!}.[/tex]
Dessa forma, utilizando essa igualdade e a igualdade [tex]\textcolor{#800000}{(iv)}[/tex] para os sucessivos valores de [tex]n[/tex], para [tex]n\gt 2 [/tex], segue que:
[tex]\qquad \dfrac {D_{2}}{2!}=\dfrac {\left(-1\right)^{2}}{2!}+\dfrac {D_{1}}{1!}[/tex]
[tex]\qquad \dfrac {D_{3}}{3!}=\dfrac {\left(-1\right)^{3}}{3!}+\dfrac {D_{2}}{(2)!}[/tex]
[tex]\qquad \dfrac {D_{4}}{4!}=\dfrac {\left(-1\right)^{4}}{4!}+\dfrac {D_{3}}{(3)!}[/tex]
[tex]\qquad \qquad \vdots[/tex]
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {\left(-1\right)^{n}}{n!}+\dfrac {D_{n-1}}{(n-1)!}[/tex],
ou ainda:
[tex]\qquad \dfrac {D_{2}}{2!}=\dfrac {1}{2!}+\dfrac {D_{1}}{1!}[/tex]
[tex]\qquad \dfrac {D_{3}}{3!}=\dfrac {-1}{3!}+\dfrac {D_{2}}{(2)!}[/tex]
[tex]\qquad \dfrac {D_{4}}{4!}=\dfrac {1}{4!}+\dfrac {D_{3}}{(3)!}[/tex]
[tex]\qquad \qquad \vdots[/tex]
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {\left(-1\right)^{n}}{n!}+\dfrac {D_{n-1}}{(n-1)!}[/tex].
Vamos somar essas [tex]n-2[/tex] igualdades:
[tex]\qquad \dfrac {D_{2}}{2!}+\dfrac {D_{3}}{3!}+\dfrac {D_{4}}{4!}+\cdots+\dfrac {D_{n}}{n!}=\\
\qquad =\dfrac {1}{2!}+\dfrac {D_{1}}{1!}+\dfrac {-1}{3!}+\dfrac {D_{2}}{(2)!}+\dfrac {1}{4!}+\dfrac {D_{3}}{(3)!}+\cdots+\dfrac {\left(-1\right)^{n}}{n!}+\dfrac {D_{n-1}}{(n-1)!}[/tex]
e mais uma vez temos vários cancelamentos a fazer, pois várias parcelas do lado esquerdo são iguais a parcelas do lado direito:
[tex]\quad \cancel{\dfrac {D_{2}}{2!}}+ \cancel{\dfrac {D_{3}}{3!}}+ \cancel{\dfrac {D_{4}}{4!}}+\cdots+\dfrac {D_{n}}{n!}=\\
\quad =\dfrac {1}{2!}+\dfrac {D_{1}}{1!}+\dfrac {-1}{3!}+ \cancel{\dfrac {D_{2}}{(2)!}}+\dfrac {1}{4!}+ \cancel{\dfrac {D_{3}}{(3)!}}+\cdots+\dfrac {\left(-1\right)^{n}}{n!}+ \cancel{\dfrac {D_{n-1}}{(n-1)!}}[/tex].
Resta, então, a seguinte igualdade:
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {1}{2!}+\dfrac {D_{1}}{1!}+\dfrac {-1}{3!}+ +\dfrac {1}{4!}+ +\cdots+\dfrac {\left(-1\right)^{n}}{n!}[/tex],
e como [tex]D_1=0[/tex], segue que:
[tex]\qquad \dfrac {D_{n}}{n!}=\dfrac {1}{2!}-\dfrac {1}{3!}+ +\dfrac {1}{4!}+ +\cdots+\dfrac {\left(-1\right)^{n}}{n!}[/tex]
[tex]\qquad D_{n}=n!\left[\dfrac {1}{2!}-\dfrac {1}{3!}+ +\dfrac {1}{4!}+ +\cdots+\dfrac {\left(-1\right)^{n}}{n!}\right][/tex].
Finalmente, sabemos que [tex]\dfrac {1}{0!}-\dfrac {1}{1!}=1-1=0[/tex]; portanto:
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=n! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dots + \dfrac{(-1)^{n}}{n!}\right]$}\, [/tex].
 |
Esperamos que você tire proveito da explanação feita aqui. |
Equipe COM – OBMEP