Desarranjo: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: fr:Analogues de la factorielle#Superfactorielle |
|||
Linha 3:
== Exemplos ==
Os dois possíveis desaranjos das três letras da palavra "lua":
* ual
* alu
Os nove possíveis desaranjos das quatro letras da palavra "cano":
* acon, anoc, aocn
* ncoa, noca, noac
* ocan, onca, onac
== Subfatoriais ==
Linha 16:
encontrar uma [[relação de recorrência]] para <math>d_n\,</math> usando o método de inclusão-exclusão.
É fácil calcular os primeiros valores de <math>d_n\,</math>:
* <math>d_1=0\,</math>
* <math>d_2=1\,</math>
* <math>d_3=2\,</math>
* <math>d_4=9\,</math>
Considere agora os possíveis desaranjos do conjunto <math>\{1,2,3,\ldots, n\}</math> e divido-os em duas classe:
# Os desaranjos em que o elemento '''n''' assume a posição de um elemento <math>k\,</math> e o elemento '''k''' assume a posição de '''n'''. Exemplo: '''1'''23'''4'''
# Os desaranjos em que o elemento '''n''' assume a posição de um elemento <math>k\,</math> e o elemento '''k''' '''não''' assume a posição de '''n'''. Exemplo: '''1'''23'''4'''
* O número de desarranjos na classe '''
* O número de desarranjos na classe '''
▲*O número de desarranjos na classe '''2''' deve ser igual ao número de desarranjos de um conjunto com <math>n-1\,</math> elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: <math>(n-1)d_{n-1}\,</math>. Para chegar a esta conclusão, observar que se o enésimo elemento assume a posição '''k''', podemos permutar '''k''' com '''n''' e realizar os desaranjos no conjunto <math>\{1,2,\ldots,k-1,k+1,k+2,\ldots,n-1,k\}</math>.
A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais:
* <math>\left\{
\begin{array}{l}
d_1=0\\
Linha 39 ⟶ 37:
== Relação com o fatorial ==
É importante observar que o [[fatorial]], <math>n!\,</math> satisfaz a mesma relação, já que:
* <math>(n-1)\left[(n-1)!+(n-2)!\right]=(n-1)(n-1)!+(n-1)!=n(n-1)!=n!</math>
Assim, é natural definir:
* <math>f_n= \frac{d_n}{n!}</math>
A seqüência <math>f_n\,</math>, assim definida satisfaz:
* <math>f_n-f_{n-1}= -\frac{1}{n}\left(f_{n-1}-f_{n-2}\right)</math>
Introduzimos, então, mais uma seqüência, <math>g_n=f_n-f_{n-1}</math>, que satisfaz:
* <math>g_n= -\frac{1}{n}g_{n-1}</math>
Como <math>g_2=f_2-f_1=d_1-\frac{1}{2}d_2=-\frac{1}{2}</math>, é fácil ver que:
* <math>g_k= \frac{(-1)^{k}}{k!},~~n\geq 2 </math>
E, portanto,
* <math>
\begin{array}{rcl}
f_n&=& f_1 + (f_2-f_1) + (f_3-f_2)+ \ldots (f_n-f_{n-1})\\
Linha 57 ⟶ 55:
</math>
Assim, obtemos, uma expressão para <math>!n\,</math>
* <math>!n=d_n=n! f_n = \sum_{k=0}^{n}(-1)^{k}\frac{n!}{k!} </math>
== Relação com o número de Euler ==
Linha 63 ⟶ 61:
<math>\sum_{k=0}^{\infty}(-1)^{k}\frac{1}{k!}=e^{-1} </math>
podemos escrever:
* <math>!n=d_n \frac{n!}{e}-\sum_{k=n+1}^{\infty}(-1)^{k}\frac{n!}{k!} </math>
O termo mais direita pode ser estimado pelo [[teste da série alternada]]:
* <math>\left|\sum_{k=n+1}^{\infty}(-1)^{k}\frac{n!}{k!}\right|\leq \frac{1}{n+1} </math>
E assim, temos:
* <math>\left|!n- \frac{n!}{e}\right|\leq \frac{1}{n+1}<1/2,~~ n\geq 2 </math>
E portanto é fácil concluir que
* <math>!n= \left[\frac{n!}{e}\right] </math>
onde <math> \left[x\right] </math> representa o inteiro mais próximo de <math>x\,</math>.
| |||