!4 (Subfatorial de 4)

 

Malba Tahan Nerd

SubFatorial $n$ pode ser calculado pela fórmula:$$!n=n!\sum _{k=0}^n\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]=

9

=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

9

Conceito

Permutações caóticas

Definição: Considere n$n$ elementos colocados em uma certa ordem definindo uma sequência que denotaremos por (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$.
Uma permutação dos elementos dessa sequência é dita uma Permutação Caótica ou um Desarranjo quando nenhum dos elementos ai$a_i$ está na sua posição original, isto é, na i$i$-ésima posição.
Denotaremos por Dn$D_n$ o número de permutações caóticas de n$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 Dn$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$n$ elementos se refira à sequência (1,2,3,⋯,n).$(1,2,3,\cdots ,n).$

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

Dn=n!⋅[10!–11!+12!–13!+⋯+(−1)nn!]$D_n=n!\cdot [{\displaystyle \frac{1}{0!}}–{\displaystyle \frac{1}{1!}}+{\displaystyle \frac{1}{2!}}–{\displaystyle \frac{1}{3!}}+\cdots +{\displaystyle \frac{(-1{)}^n}{n!}}]$.

Para calcularmos o número Dn$D_n$ de permutações caóticas da sequência ordenada (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$, vamos denotar por:

• C$C$ o conjunto de todas as permutações dos elementos de (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$;
• C1$C_1$ o conjunto das permutações de (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$ nas quais o elemento a1$a_1$ ocupa o primeiro lugar na sequência;
• C2$C_2$ o conjunto das permutações dos elementos de (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$ nas quais o elemento a2$a_2$ ocupa o segundo lugar na sequência;
• Ci$C_i$ o conjunto das permutações dos elementos de (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$ nas quais o elemento genérico ai$a_i$ ocupa o lugar i$i$ na sequência,

e por c,c1,c2,⋯,cn$c,c_1,c_2,\cdots ,c_n$ o número de elementos dos conjuntos C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,C_n$, respectivamente.
Observe que
► Dn$D_n$ será o número de sequências de C$C$ que pertencem a exatamente ZERO dos conjuntos C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,C_n$;
assim, do total c$c$ de todas as permutações de (a1,a2,a3,⋯,an)$(a_1,a_2,a_3,\cdots ,a_n)$, devemos subtrair as sequências que pertencem a, pelo menos, um dos conjuntos C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,C_n$.
Vamos lá!
(1)$(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 C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,C_n$. Portanto, devemos inicialmente subtrair de c$c$ o número de elementos desses conjuntos. Considere, então a seguinte diferença:
X1=c−c1−c2−⋯−cn$X_1=c-c_1-c_2-\cdots -c_n$.
Veja que em cada conjunto Ci$C_i$, fixamos apenas o elemento ai$a_i$ na posição i$i$; as demais n−1$n-1$ posições podem ser ocupadas por quaisquer dos elementos restantes da sequência original. Com isso, temos que cada ci$c_i$ é o número de permutações de n−1$n-1$ elementos, ou seja,
c1=c2=⋯=cn=Pn−1=(n−1)!$c_1=c_2=\cdots =c_n=P_{n-1}=(n-1)!$.
Portanto, seque que:
X1=c−c1−c2−⋯−cn=c−(c1+c2+⋯+cn)X1=c−⎡⎣⎢(n−1)!+(n−1)!+⋯+(n−1)!n vezes ⎤⎦⎥X1=c−n⋅(n−1)!$$\begin{gathered} X_1=c-c_1-c_2-\cdots -c_n=c-(c_1+c_2+\cdots +c_n) \\ {X}_1=c-\left[\underset{n\text{ vezes }}{\underbrace{(n-1)!+(n-1)!+\cdots +(n-1)!}}\right] \\ {X}_1=c-n\cdot (n-1)! \end{gathered}$$.
Terminamos? Dn=X1$D_n=X_1$?
Não!
(2)$(2)$ Observe que várias sequências de C$C$ foram subtraídas mais de uma vez. Com efeito, sequências do tipo (−−,a2,a3,−−⋯,−− )$(\underset{\_}{},a_2,a_3,\underset{\_}{}\cdots ,\underset{\_}{})$, por exemplo, foram retiradas da nossa contagem pelo menos duas vezes: como elementos de C2$C_2$ e como elementos de C3$C_3$. Assim, precisamos acrescentar na nossa contagem o número de sequências que estão nas interseções do tipo Ci∩Cj$C_i\cap C_j$, para i≠j$i\ne j$. E que número é esse?

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

Assim, devemos acrescentar à nossa contagem n!(n−2)!2!⋅(n−2)!=n!2!${\displaystyle \frac{n!}{(n-2)!2!}}\cdot (n-2)!={\displaystyle \frac{n!}{2!}}$ sequências que foram indevidamente retiradas. Obtemos então uma segunda contagem parcial das permutações caóticas:
X2=X1+n!2!X2=c−n!+n!2!$$\begin{gathered} X_2=X_1+{\displaystyle \frac{n!}{2!}} \\ {X}_2=c-n!+{\displaystyle \frac{n!}{2!}} \end{gathered}$$.
Terminamos? Dn=X2$D_n=X_2$?
De novo, Não!
(3)$(3)$ Observe que, agora, várias sequências foram acrescentadas a mais …
Com efeito, sequências do tipo (−−,a2,a3,a4,−−⋯,−− )$(\underset{\_}{},a_2,a_3,a_4,\underset{\_}{}\cdots ,\underset{\_}{})$, por exemplo, foram contadas na nossa contagem pelo menos três vezes: como elementos de C2∩C3$C_2\cap C_3$, como como elementos de C2∩C4$C_2\cap C_4$ e como elementos de C3∩C4$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 Ci∩Cj∩Ck$C_i\cap C_j\cap C_k$, para i≠j<k$i\ne j<k$. E que número é esse?

Fixados i$i$, j$j$ e k$k$, com 1⩽i<j<k⩽n$1⩽i<j<k⩽n$, as sequências que estão em Ci$C_i$, em Cj$C_j$ e em Ck$C_k$ têm três posições fixas, a i$i$-ésima, j$j$-ésima e k$k$-ésima posições, e as n−3$n-3$ demais são livres. Temos então Pn−3=(n−3)!$P_{n-3}=(n-3)!$ sequências em cada interseção Ci∩Cj∩Ck$C_i\cap C_j\cap C_k$.
Quantas dessas interseções temos? Como Ci∩Cj∩Ck$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$n$ elementos tomados 3$3$ a 3$3$: Cn,3=n!(n−3)!3!$C_{n,3}={\displaystyle \frac{n!}{(n-3)!3!}}$.

Vamos, então, subtrair da nossa contagem n!(n−3)!3!⋅(n−3)!=n!3!${\displaystyle \frac{n!}{(n-3)!3!}}\cdot (n-3)!={\displaystyle \frac{n!}{3!}}$ sequências que foram indevidamente acrescentadas. Obtemos então uma terceira contagem parcial das permutações caóticas:
X3=X2−n!3!X3=c−n!+n!2!−n!3!$$\begin{gathered} X_3=X_2-{\displaystyle \frac{n!}{3!}} \\ {X}_3=c-n!+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}} \end{gathered}$$.
Agora terminamos? Dn=X3$D_n=X_3$?
Bom,aí vai depender…
(4)$(4)$ Se tivermos interseções de quatro conjuntos distintos dentre C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,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 n!4!${\displaystyle \frac{n!}{4!}}$ sequências à nossa última contagem, obtendo:
X4=X3+n!4!X4=c−n!+n!2!−n!3!+n!4!.$$\begin{gathered} X_4=X_3+{\displaystyle \frac{n!}{4!}} \\ {X}_4=c-n!+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}}+{\displaystyle \frac{n!}{4!}}. \end{gathered}$$
E prosseguimos com contagens parciais
Xk=c−n!+n!2!−n!3!+n!4!+⋯+(−1)kn!k!$X_k=c-n!+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}}+{\displaystyle \frac{n!}{4!}}+\cdots +{(-1)}^k{\displaystyle \frac{n!}{k!}}$,
até considerarmos a maior interseção possível de conjuntos distintos dentre C1,C2,C3,⋯,Cn$C_1,C_2,C_3,\cdots ,C_n$ que é a interseção C1∩C2∩C3∩⋯∩Cn$C_1\cap C_2\cap C_3\cap \cdots \cap C_n$, da qual faz parte apenas a sequência original (a1,a2,⋯,an)$(a_1,a_2,\cdots ,a_n)$.
Pelo exposto, temos que:
Dn=c−n!+n!2!−n!3!+n!4!+⋯+(−1)kn!k!+⋯+(−1)nn!n!$D_n=c-n!+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}}+{\displaystyle \frac{n!}{4!}}+\cdots +{(-1)}^k{\displaystyle \frac{n!}{k!}}+\cdots +{(-1)}^n{\displaystyle \frac{n!}{n!}}$
e, como c$c$ é o número de permutações dos n$n$ elementos a1,a2,a3,⋯,an$a_1,a_2,a_3,\cdots ,a_n$ que formam as sequências, segue que:
Dn=n!−n!+n!2!−n!3!+n!4!+⋯+(−1)nn!n!$D_n=n!-n!+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}}+{\displaystyle \frac{n!}{4!}}+\cdots +{(-1)}^n{\displaystyle \frac{n!}{n!}}$.
Mas 0!=1$0!=1$ e 1!=1$1!=1$; portanto, finalmente podemos concluir que:
Dn=n!0!−n!1!+n!2!−n!3!+n!4!+⋯+(−1)nn!n!$D_n={\displaystyle \frac{n!}{0!}}-{\displaystyle \frac{n!}{1!}}+{\displaystyle \frac{n!}{2!}}-{\displaystyle \frac{n!}{3!}}+{\displaystyle \frac{n!}{4!}}+\cdots +{(-1)}^n{\displaystyle \frac{n!}{n!}}$
Dn=n!⋅[10!–11!+12!–13!+⋯+(−1)nn!]$D_n=n!\cdot [{\displaystyle \frac{1}{0!}}–{\displaystyle \frac{1}{1!}}+{\displaystyle \frac{1}{2!}}–{\displaystyle \frac{1}{3!}}+\cdots +{\displaystyle \frac{(-1{)}^n}{n!}}]$.