terça-feira, 28 de setembro de 2021

!4 (Subfatorial de 4)

Malba Tahan Nerd

SubFatorial $n$ pode ser calculado pela fórmula: $! n = n! n \sum k = 0 \frac{(- 1)^{k}}{k!}$

!4[(-1^0)/0!+(-1^1)/1!+(-1^2)/2!+(-1^3)/3!+(-1^4)/4!)=

24[1/1-1/1+1/2-1/6+1/24]=

!24[~~1-1~~+1/2-1/6+1/24]=

!24[1/2-1/6+1/24]=

MMC = 24 Ok?

24[12/24 -4/24+1/24]=

24[9/24]=

=4!×(1/1−1/1+1/2−1/6+1/24)=24×9/24=9

Outra fórmula:

!n=[n!e]

!4 = 24/e

e = 2,718

24/2,718

8,8291

Arredondando

Conceito

Permutações caóticas

Definição: Considere

n

elementos colocados em uma certa ordem definindo uma sequência que denotaremos por

(a_{1}, a_{2}, a_{3}, \dots, a_{n})

.
Uma permutação dos elementos dessa sequência é dita uma Permutação Caótica ou um Desarranjo quando nenhum dos elementos

a_{i}

está na sua posição original, isto é, na

i

-ésima posição.
Denotaremos por

D_{n}

o número de permutações caóticas de

n

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

D_{n}

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

n

elementos se refira à sequência

(1, 2, 3, \dots, n) .

A nossa discussão inicial será sobre uma justificativa da fórmula para o número de permutações caóticas $D_{n}$ apresentada na Sala inicial :

$D_{n} = n! \cdot [\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(- 1)^{n}}{n!}]$ .

Para calcularmos o número

D_{n}

de permutações caóticas da sequência ordenada

(a_{1}, a_{2}, a_{3}, \dots, a_{n})

, vamos denotar por:

$C$ o conjunto de todas as permutações dos elementos de $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ ;
$C_{1}$ o conjunto das permutações de $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ nas quais o elemento $a_{1}$ ocupa o primeiro lugar na sequência;
$C_{2}$ o conjunto das permutações dos elementos de $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ nas quais o elemento $a_{2}$ ocupa o segundo lugar na sequência;
$C_{i}$ o conjunto das permutações dos elementos de $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ nas quais o elemento genérico $a_{i}$ ocupa o lugar $i$ na sequência,

e por $c, c_{1}, c_{2}, \dots, c_{n}$ o número de elementos dos conjuntos $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ , respectivamente.
Observe que
► $D_{n}$ será o número de sequências de $C$ que pertencem a exatamente ZERO dos conjuntos $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ ;
assim, do total $c$ de todas as permutações de $(a_{1}, a_{2}, a_{3}, \dots, a_{n})$ , devemos subtrair as sequências que pertencem a, pelo menos, um dos conjuntos $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ .
Vamos lá!
$(1)$ 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 $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ . Portanto, devemos inicialmente subtrair de $c$ o número de elementos desses conjuntos. Considere, então a seguinte diferença:
$X_{1} = c - c_{1} - c_{2} - \dots - c_{n}$ .
Veja que em cada conjunto $C_{i}$ , fixamos apenas o elemento $a_{i}$ na posição $i$ ; as demais $n - 1$ posições podem ser ocupadas por quaisquer dos elementos restantes da sequência original. Com isso, temos que cada $c_{i}$ é o número de permutações de $n - 1$ elementos, ou seja,
$c_{1} = c_{2} = \dots = c_{n} = P_{n - 1} = (n - 1)!$ .
Portanto, seque que:
$X_{1} = c - c_{1} - c_{2} - \dots - c_{n} = c - (c_{1} + c_{2} + \dots + c_{n}) X_{1} = c - [\underset{n vezes}{\underset{⏟}{(n - 1)! + (n - 1)! + \dots + (n - 1)!}}] X_{1} = c - n \cdot (n - 1)!$ .
Terminamos? $D_{n} = X_{1}$ ?
Não!
$(2)$ Observe que várias sequências de $C$ foram subtraídas mais de uma vez. Com efeito, sequências do tipo $(\underline{}, a_{2}, a_{3}, \underline{} \dots, \underline{})$ , por exemplo, foram retiradas da nossa contagem pelo menos duas vezes: como elementos de $C_{2}$ e como elementos de $C_{3}$ . Assim, precisamos acrescentar na nossa contagem o número de sequências que estão nas interseções do tipo $C_{i} \cap C_{j}$ , para $i \neq j$ . E que número é esse?

Fixados $i$ e $j$ , com $1 ⩽ i < j ⩽ n$ , as sequências que estão em $C_{i}$ e em $C_{j}$ têm duas posições fixas, a $i$ -ésima e $j$ -ésima posições, e as $n - 2$ demais são livres. Temos então $P_{n - 2} = (n - 2)!$ sequências em cada interseção $C_{i} \cap C_{j}$ .
Mas quantas dessas interseções nós temos? Como $C_{i} \cap C_{j} = C_{j} \cap C_{i}$ , a quantidade de interseções é o número de Combinações Simples de $n$ elementos tomados $2$ a $2$ : $C_{n, 2} = \frac{n!}{(n - 2)! 2!}$ .

Assim, devemos acrescentar à nossa contagem $\frac{n!}{(n - 2)! 2!} \cdot (n - 2)! = \frac{n!}{2!}$ sequências que foram indevidamente retiradas. Obtemos então uma segunda contagem parcial das permutações caóticas:
$X_{2} = X_{1} + \frac{n!}{2!} X_{2} = c - n! + \frac{n!}{2!}$ .
Terminamos? $D_{n} = X_{2}$ ?
De novo, Não!
$(3)$ Observe que, agora, várias sequências foram acrescentadas a mais …
Com efeito, sequências do tipo $(\underline{}, a_{2}, a_{3}, a_{4}, \underline{} \dots, \underline{})$ , por exemplo, foram contadas na nossa contagem pelo menos três vezes: como elementos de $C_{2} \cap C_{3}$ , como como elementos de $C_{2} \cap C_{4}$ e como elementos de $C_{3} \cap C_{4}$ . Poxa, agora vamos precisar tirar da nossa contagem o número de sequências que estão nas interseções do tipo $C_{i} \cap C_{j} \cap C_{k}$ , para $i \neq j < k$ . E que número é esse?

Fixados $i$ , $j$ e $k$ , com $1 ⩽ i < j < k ⩽ n$ , as sequências que estão em $C_{i}$ , em $C_{j}$ e em $C_{k}$ têm três posições fixas, a $i$ -ésima, $j$ -ésima e $k$ -ésima posições, e as $n - 3$ demais são livres. Temos então $P_{n - 3} = (n - 3)!$ sequências em cada interseção $C_{i} \cap C_{j} \cap C_{k}$ .
Quantas dessas interseções temos? Como $C_{i} \cap C_{j} \cap C_{k}$ independe da ordem dos três conjuntos, a quantidade de interseções é o número de Combinações Simples de $n$ elementos tomados $3$ a $3$ : $C_{n, 3} = \frac{n!}{(n - 3)! 3!}$ .

Vamos, então, subtrair da nossa contagem $\frac{n!}{(n - 3)! 3!} \cdot (n - 3)! = \frac{n!}{3!}$ sequências que foram indevidamente acrescentadas. Obtemos então uma terceira contagem parcial das permutações caóticas:
$X_{3} = X_{2} - \frac{n!}{3!} X_{3} = c - n! + \frac{n!}{2!} - \frac{n!}{3!}$ .
Agora terminamos? $D_{n} = X_{3}$ ?
Bom,aí vai depender…
$(4)$ Se tivermos interseções de quatro conjuntos distintos dentre $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ , então retiramos da nossa última contagem parcial mais sequências do que devíamos. Essas sequências deverão ser recontadas e acrescentaremos $\frac{n!}{4!}$ sequências à nossa última contagem, obtendo:
$X_{4} = X_{3} + \frac{n!}{4!} X_{4} = c - n! + \frac{n!}{2!} - \frac{n!}{3!} + \frac{n!}{4!} .$
E prosseguimos com contagens parciais
$X_{k} = c - n! + \frac{n!}{2!} - \frac{n!}{3!} + \frac{n!}{4!} + \dots + {(- 1)}^{k} \frac{n!}{k!}$ ,
até considerarmos a maior interseção possível de conjuntos distintos dentre $C_{1}, C_{2}, C_{3}, \dots, C_{n}$ que é a interseção $C_{1} \cap C_{2} \cap C_{3} \cap \dots \cap C_{n}$ , da qual faz parte apenas a sequência original $(a_{1}, a_{2}, \dots, a_{n})$ .
Pelo exposto, temos que:
$D_{n} = c - n! + \frac{n!}{2!} - \frac{n!}{3!} + \frac{n!}{4!} + \dots + {(- 1)}^{k} \frac{n!}{k!} + \dots + {(- 1)}^{n} \frac{n!}{n!}$
e, como $c$ é o número de permutações dos $n$ elementos $a_{1}, a_{2}, a_{3}, \dots, a_{n}$ que formam as sequências, segue que:
$D_{n} = n! - n! + \frac{n!}{2!} - \frac{n!}{3!} + \frac{n!}{4!} + \dots + {(- 1)}^{n} \frac{n!}{n!}$ .
Mas $0! = 1$ e $1! = 1$ ; portanto, finalmente podemos concluir que:
$D_{n} = \frac{n!}{0!} - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \frac{n!}{4!} + \dots + {(- 1)}^{n} \frac{n!}{n!}$
$D_{n} = n! \cdot [\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(- 1)^{n}}{n!}]$ .