A - Question introductive

Il s'agit de calculer P3.

Par définition, P3=(1-P3barre). Or P3barre est l'événément "aucune lettre n'arrive à son destinataire".

Soit W l'ensemble des envois possibles : card (W)=3!=6

Si on appelle 1, 2 et 3 les lettres et A, B et C les destinataires, pour réaliser P3barre il faut :

• soit que 1 soit envoyé à B. La seule possibilité est alors que 3 soit envoyée à A et 2 à C
• soit que 1 soit envoyé à C. La seule possibilité est alors que 3 soit envoyée à B et 2 à A

On a alors card(P3barre)=2

Soit P3barre=card(P3barre)/card (W)=2/6=1/3

On a enfin P3=(1-P3barre)=2/3

B - Nombre de permutations sans point fixe de n éléments

1) D1=0 (en effet, il est impossible de ne pas associer un seul élément à lui-même)

D2=1 (en effet, il n'y a que deux possibilités : soit les deux éléments correspondent, soit ils sont interchangés)

2) Pour réaliser un dérangement de n éléments, on a forcément p(1)¹1

On peut alors réaliser une partition de l'ensemble des dérangements en fonction de p(1) :

• soit p(1)=2, il y a alors bn possibilités. (Remarque : bn=Dn-1 car il faut réaliser un dérangement de [2,n], qui a n-1 éléments)
• soit p(1)=3, il y a alors également bn possibilités (il reste toujours n-1 éléments)
• soit p(1)=4, ...
• ....
• soit p(1)=n

Au final, Dn est la somme des cardinaux des ensembles précités. Comme il y a n-1 possibilités pour p(1) et que celles-ci comprennent chacune bn cas, on a bien :

Dn=(n-1)bn

3) On veut réaliser un dérangement de [1,n] tel que p(1)=2 et p(2)=1. Il faut alors réaliser un dérangement de [3,n], qui a n-2 éléments.

Or réaliser un dérangement de [3,n] (sur lui-même) revient à réaliser un dérangement de [1,n-2] sur lui-même (car [3,n] et [1,n-2] sont bijectifs, c'est à dire qu'il faut et il suffit de renuméroter les éléments pour passer de l'un à l'autre).

Au final :

• il y a une et une deule façon de réaliser p(1)=2 et p(2)=1
• il y a Dn-2 façons de réaliser un dérangement de [3,n],

On a donc bien 1.Dn-2=Dn-2 façons de réaliser un dérangement de [1,n] tel que p(1)=2 et p(2)=1.

4)

a) Comme au 3) On veut réaliser une permutation de [1,n] tel que 1 soit le seul point fixe. Il faut alors réaliser un dérangement de [2,n], qui a n-1 éléments.

Or réaliser un dérangement de [2,n] (sur lui-même) revient à réaliser un dérangement de [1,n-1] sur lui-même (car [2,n] et [1,n-1] sont bijectifs, c'est à dire qu'il faut et il suffit de renuméroter les éléments pour passer de l'un à l'autre).

Au final :

• il y a une et une deule façon de réaliser p(1)=1
• il y a Dn-1 façons de réaliser un dérangement de [2,n],

On a donc bien 1.Dn-1=Dn-1 façons de réaliser une permutation de [1,n] tel que 1 soit le seul point fixe.

b) Etudions top :

• top(1)=t(p(1))=t(2)=1
• top(2)=t(p(2)). Or p(2)¹1 (et p(2)¹2, car p est un dérangement). On sait que t laisse fixe les points > 2. On a donc top(2)=p(2)>3 donc top(2)¹2
• pour k>2, top(k)=p(k)¹k (car p(k)>2 donc t(p(k))=p(k))

top est donc bien une permutation qui laisse fixe 1 et dérange les autre points

c) Par 4a), on sait qu'il y a Dn-1 permutations dont le seul point fixe est 1. Il y a donc Dn-1 façons de construire top. Or il n'y a qu'une seule application t et p est relié à top par t. Il y a donc le même nombre de façons de construire p que de construire top.

Il y a donc Dn-1 permutations p sans point fixe telles que p(1)=2 et p(2)¹ 1

5) Par 2), on sait que Dn=(n-1)bn, où bn est le nombre de permutations telles que p(1)=2.

Ces permutations peuvent être de deux types :

• soit p(1)=2 et p(2)=1 (Dn-2 possibilités)
• soit p(1)=2 et p(2)¹ 1 (Dn-1 possibilités)

On a donc bn=Dn-1+Dn-2

Soit Dn=(n-1)bn=(n-1)(Dn-1+Dn-2) (pour n>3)

6)

a) an=Dn-nDn-1=(n-1)(Dn-1+Dn-2)-nDn-1=-Dn-1+(n-1)Dn-2 =-an-1

b) Par récurrence : a2=D2-2D1=1=(-1)² (cf 1))

Soit n>=2 tel que an=(-1)^n

On a alors an+1=-an=-(-1)^n=(-1)^(n+1)

Par le principe de récurrence, on a alors an=(-1)^n pour tout n>1

c) Par hypothèse, on a Dn=an+nDn-1=nDn-1+(-1)^n

d) Il suffit ici de faire un raisonnement par récurrence en utilisant D1 et 6c)

7) D3/3!=1/2!-1/3!=1/2-1/6=1/3

Soit D3=1/3.6=2

Calculs similaires pour D4 et D5...

8) Ici, plutôt que de calculer, il est préférable d'utiliser la relation de récurrence du 6c)

9) Je te laisse calculer les valeurs et remplir le tableau...

Le calcul de lim(un) (apparemment non demandé ici) est assez complexe. (on passe généralement par la notion de série, qui n'est pas au programme). Le résultat est e/(1-2e)