Je donne déjà la 1ère démonstration puisqu'il n'y a que de l'écriture. Il y a pas besoin de plus de connaissance que ça en math ou quoi, il y a juste besoin de temps pour bien comprendre.
Donc on cherche le nombre de configuration où aucun élément n'est à sa place. On numérote les éléments de 1 à n, et 1 doit aller à la place 1, 2 à la place 2, etc
-Si on commence par placer un élément en 1, on a n-1 choix puisqu'il ne faut pas placer 1 en 1. On place l'élément k à la place n°1.
Maintenant il faut faire la différence entre 2 cas :
(1) -On place l'élément 1 à la place n°k
(2) -On ne place pas l'élément 1 à la place n°k
Pour (1) : on a donc permuter 1 et k, et le problème revient maintenant à chercher le nombre de configuration à n-2 éléments avec n-2 places où aucun élément ne doit être à sa place.
Pour (2) : situation : on a placé l'élément k (en n°1), on a placé un élément différent de 1 en k.
Maintenant il faut placer n-2 éléments de tel sorte que aucun ne soit à sa place, mais il y a un élément particulier : 1. En effet, sa place est déjà prise puisque k est à la place n°1.
Donc le problème revient à placer n-2 éléments sachant qu'il y en a un qui n'a pas de place ! Ce problème est différent de celui où il faut placer des éléments sachant que TOUS ont une place puisque maintenant un élément n'a pas de place interdite.
Regardons un exemple du problème pour 3 éléments : 1,2,3 et disons que 1 n'a pas de place, et dont qu'
il peut aller n'importe où :
il y a 3 combinaisons où aucun élément n'est à sa place :
1 3 2
2 3 1
3 1 2
Alors que si on considère que 1 à une place, la place n°1, alors le nombre de configurations est 2 : 2 3 1 et 3 1 2.
On a bien un nombre différent de place suivant que tous les éléments ont une place interdite où qu'un des éléments n'a pas de place interdite.
Donc on note
P(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que chaque élément a une place.
Et on note
Q(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que n-1 éléments ont une place, et
qu'un élément n'a aucune place.
( Remarque : il y a toujours n places, puisqu'il y a toujours n éléments à placer, cela veut dire qu'il y a en fait une place "libre" où tout le monde peut aller. )
Pour résumer P(n) = (1) + (2) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
On cherche maintenant une autre relation du même type sur Q(n).
Le problème : il y a n éléments et n places. Il a n-1 éléments qui ont une place interdite, 1 élément qui n'a aucune place interdite, et il y a donc une place qui peut accepter n'importe qui.
Soit A l'élément qui n'a pas de place interdite. Soit B le n° de la place où tout le monde peut aller.
Il y a encore 2 cas à distinguer :
(1) Si on place l'élément A à la place B, alors le problème revient à P(n-1).
(2) Si on ne place pas l'élément A à la place B (il y a n-1 choix différents), alors il y a toujours l'élément A qui n'a pas de place interdite et qui doit être placer quand même, donc le problème revient à Q(n-1).
D'où : Q(n) = (1) + (2) = P(n-1) + (n-1)*Q(n-1)
Finalement on a le système :
P(n) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
Q(n) = P(n-1) + (n-1)Q(n-1)
en simplifiant :
P(n) = (n-1)*Q(n-1)
Q(n) = (n-1)*Q(n-1) + Q(n-2)*(n-2) = P(n) + P(n-1)
puis finalement :
P(n) = (n-1)*P(n-1) + (n-1)*P(n-2)
Maintenant commence la démonstration : (juste du jeu d'écriture)
P(n) - n*P(n-1) = -P(n-1) + (n-1)*P(n-2) = - [ P(n-1) - (n-1)*P(n-2) ]
On pose A(n)= P(n) - n*P(n-1)
On a donc A(n) = -A(n-1)
On a A(2) = P(2) - 2*P(1), avec P(2)=1 et P(1)=0 cela donne A(2)=1
Donc par récurrence : A(n)=(-1)^n
Donc : A(n) = P(n) - n*P(n-1) = (-1)^n
On divise par n!
P(n)/n! = P(n-1)/(n-1)! + (-1)^n
On pose B(n) = P(n)/n!
On a donc : B(n) = B(n-1) + (-1)^n
Par récurrence : B(n) = Somme de k=0 à k=n de (-1)^k
Et puisque P(n) = n!*B(n) on a le résultat :
P(n) = n! * [ Somme de k=0 à k=n de (-1)^k ]
En espérant avoir été clair et concis