Niveau Maths sup

denombrement

Posté par (invité) 03-01-04 à 23:44

Soient n et k, 2 entiers naturels tels que 0<ou=k<ou=n.
On note I(k,n) le nombre de permutations de l'ensemble [1,n] admettant
exactement k points fixes (ou "points invariants"). On convient
que I(0,0)=1
1)Calculer I(n,n);I(n-1,n)(pour n>ou=1);I(n-2,n)(pour n>ou=2)
2)Que vaut sigma(I(k,n))de k=0 à n?
3)Montrer que I(k,n)=C(k,n)*I(0,n-k)
(C(k,n)=nombre de combinaisons de k elements pris parmi n)
4)Construire une table des I(k,n) pour 0<ou=k<ou=n<ou=6
5)a)Combien y a-t-il de permutations laissant fixe un element de [1,n] donné?

b)En déduire la somme sigma(k*I(k,n))de k=0 à n.
(Calculez de 2 façons le nombre total de points fixes de toutes les permutations).

c)Quel est le nombre moyen de points invariants d'une permutation de
[1,n]?
6)Montrer que (sigma(C(k,n)*I(0,k))de k=0 à n)=n!
7)On a ainsi
I(0,n+1)=(n+1)!-(sigma(C(k,n+1)*I(0,k))de k=0 à n)
En deduire, par recurrence forte (H1 vraie et pour tout n entier naturel,H1,H2,...,Hn
entrainent H(n+1)), que quel que soit n entier naturel different
de 0,
I(0,n)=n*I(0,n-1)+(-1)^n
Dresser une table des I(0,n), pour n de 0 à 10.
8)Montrer que, pour tout n entier naturel, on a
I(0,n)=n!*(sigma((-1)^k/(k!))de k=0 à n).

Posté par re : denombrement 28-06-10 à 15:00

Bonjour,

Un très ancien topic qui m' a paru intéressant. Voici une solution susceptible d' être utile:

1) $I(n,n)$ est le nombre de permutations de $[1,\cdots ,n]$ admettant $n$ points fixes. Seule l' identité laisse $n$ points fixes invariants.

$\fbox{I(n,n)=1}$

Il n' y a aucune permutation de $[1,\cdots ,n]$ admettant $n-1$ points fixes:

$\fbox{I(n-1,n)=0}$

$I(n-2,n)$ est le nombre de permutations admettant $n-2$ points fixes.

Des permutations de ce type échangent 2 points non fixes de $[1,\cdots ,n]$ .

Le nombre de ces permutations est le nombre de manières de choisir 2 points parmi les $n$ :

$\fbox{I(n-2,n)=\left(n\\2\right)=\frac{n(n-1)}{2}}$

2) $\Bigsum_{k=0}^nI(k,n)$ est le nombre de permutations de $[1,\cdots ,n]$ :

$\fbox{\Bigsum_{k=0}^nI(k,n)=n!}$

3) Pour former une permutation admettant $k$ points fixes, on choisit $n-k$ points non fixes parmi $n$ et le nombre de permutations de ces $n-k$ points est $I(0,n-k)$ :

d' où: $I(k,n)=\left(n\\n-k\right)I(0,n-k)$ puis avec $\left(n\\n-k\right)=\left(n\\k\right)$ :

$\fbox{I(k,n)=\left(n\\k\right)I(0,n-k)}$

4) Les résultats précédents permettent de construire une table pour $0\leq k\leq n\leq 6$ :

$n$ \ $k$	0	1	2	3	4	5	6	$n!$
0	1							1
1	0	1						1
2	1	0	1					2
3	2	3	0	1				6
4	9	8	6	0	1			24
5	44	45	20	10	0	1		120
6	265	264	135	40	15	0	1	720

5)a) Il y a $(n-1)!$ permutations laissant fixe un élément de $[1,\cdots ,n]$ donné; ce sont les permutations d' un ensemble de $n-1$ éléments.

5)b) D' une part, le nombre de points fixes des permutations de $[1,\cdots ,n]$ laissant fixes $k$ points est $kI(k,n)$

Le nombre total de points fixes de toutes les permutations de $[1,\cdots ,n]$ est donc $\Bigsum_{k=0}^nkI(k,n)$

D' autre part, d' après la question 5)a), ce nombre total de points fixes est $n(n-1)!=n!$ .

On en déduit:

$\fbox{\Bigsum_{k=0}^nkI(k,n)=n!}$

5)c) Le nombre moyen $m$ de points invariants d' une permutation de $[1,\cdots ,n]$ est donc $\fbox{m=1}$

6) $\Bigsum_{k=0}^n\left(n\\k\right)I(0,k)=\Bigsum_{k=0}^n\left(n\\n-k\right)I(0,n-k)$

$\Bigsum_{k=0}^n\left(n\\k\right)I(0,k)=\Bigsum_{k=0}^n\left(n\\k\right)I(0,n-k)$

$\Bigsum_{k=0}^n\left(n\\k\right)I(0,k)=\Bigsum_{k=0}^nI(k,n)$ d' après 3)

d' où:

$\fbox{\Bigsum_{k=0}^n\left(n\\k\right)I(0,k)=n!}$

7) On a donc effectivement:

$\Bigsum_{k=0}^{n+1}\left(n+1\\k\right)I(0,k)=(n+1)!$

$I(0,n+1)+\Bigsum_{k=0}^n\left(n+1\\k\right)I(0,k)=(n+1)!$

d' où la relation que l' on utilisera dans la récurrence qui suit:

$\fbox{I(0,n+1)=(n+1)!-\Bigsum_{k=0}^n\left(n+1\\k\right)I(0,k}$ (1)

On fait maintenant une récurrence forte sur la propriété $P_n$ :

Pour tout entier naturel $n$ non nul: $I(0,n)=nI(0,n-1)+(-1)^n$

Initialisation:

On a bien $I(0,1)=I(0,0)-1$ et $P_1$ est vraie.

Hérédité:

On suppose que pour tout entier naturel $k$ non nul tel que $k\leq n$ , on a:

$I(0,k)=kI(0,k-1)+(-1)^k$

Alors:

$I(0,n+1)=(n+1)!-\Bigsum_{k=0}^n\left(n+1\\k\right)I(0,k)$ d' après (1)

$I(0,n+1)=(n+1)!-\Bigsum_{k=0}^n\left(n+1\\k\right)\left[kI(0,k-1)+(-1)^k\right]$ (hypothèse de récurrence)

$I(0,n+1)=(n+1)!-\Bigsum_{k=0}^nk\left(n+1\\k\right)I(0,k-1)-\Bigsum_{k=0}^n\left(n+1\\k\right)(-1)^k$

$I(0,n+1)=(n+1)!-(n+1)\Bigsum_{k=1}^n\left(n\\k-1\right)I(0,k-1)-\Bigsum_{k=0}^{n+1}\left(n+1\\k\right)(-1)^k+(-1)^{n+1}$

$I(0,n+1)=(n+1)!-(n+1)\Bigsum_{k=0}^{n-1}\left(n\\k\right)I(0,k)-(-1+1)^{n+1}+(-1)^{n+1}$

$I(0,n+1)=(n+1)\left[n!-\Bigsum_{k=0}^{n-1}\left(n\\k\right)I(0,k)\right]+(-1)^{n+1}$

$I(0,n+1)=(n+1)I(0,n)+(-1)^{n+1}$ et l' hérédité est prouvée.

On a donc pour tout $n$ entier naturel non nul:

$\fbox{I(0,n)=nI(0,n-1)+(-1)^n}$

Formule qui permet de construire une table des $I(0,n)$ pour $0\leq n\leq 10$ :

$n$	0	1	2	3	4	5	6	7	8	9	10
$I(0,n)$	1	0	1	2	9	44	[265	1854	14833	133496	1334961

8) Une récurrence sur la propriété $P_n$ :

Pour tout entier naturel $n$ , $I(0,n)=n!\Bigsum_{k=0}^n\frac{(-1)^k}{k!}$

Initialisation:

On a bien $I(0,0)=0!\times 1=1$ et $P_0$ est vraie.

$Hérédité:$

On suppose que $I(0,n)=n!\Bigsum_{k=0}^n\frac{(-1)^k}{k!}$ pour un certain rang $n$ fixé.

Alors: $I(0,n+1)=(n+1)I(0,n)+(-1)^{n+1}$ d' après la question précédente.

$I(0,n+1)=(n+1)!\Bigsum_{k=0}^n\frac{(-1)^k}{k!}+(-1)^{n+1}$ (hypothèse de récurrence)

$I(0,n+1)=(n+1)!\Bigsum_{k=0}^{n+1}\frac{(-1)^k}{k!}$ et l' hérédité est prouvée.

Donc pour tout $n$ entier naturel: $\fbox{I(0,n)=n!\Bigsum_{k=0}^n\frac{(-1)^k}{k!}}$

Posté par re : denombrement 28-06-10 à 15:08

Wouaw, tous ces efforts pour un topic d'il y a 6 ans??

Salut cailloux , et bravo, quelle abnégation!

Posté par re : denombrement 28-06-10 à 15:13

Bonjour Tigweg,

... ou du temps à perdre

Posté par re : denombrement 29-06-10 à 22:05

bonsoir cailloux
cette question sort assez souvent mais en général on utilise la formule du crible qui n'est pas plus drôle à écrire
en général cela se termine par"on permute au hasard les n entiers de [|1;n|],on note X_n la variable aléatoire égale au nombre de points fixes de cette permutation aléatoire,donnez la loi de X_n"
je n'avais pas vu passer ce topic,je viens de comprendre pourquoi:je n'étais pas encore arrivée sur l'ile
je vais le mettre dans mes favoris,j'ai une petite fille qui entre en prépa hec cela pourra lui être utile merci d'avoir fait les calculs

bonsoir Tigweg

Posté par re : denombrement 29-06-10 à 22:23

Bonsoir veleda,

Je ne pensais pas que ce topic se révélerait "utile" si vite

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

algèbre en post-bac
28 fiches de mathématiques sur "algèbre" en post-bac disponibles.

Rechercher

Espace membre

Zone membre

Pas de compte ?
Je m'inscris

Changer d'île

Cours et Exercices de maths

Forum de maths

college

lycee

Outils de maths

Pages les plus populaires

denombrement

Seuls les membres peuvent poster sur le forum !

Ce topic

Fiches de maths