EXEMPLES DE PROBLEMES DE DENOMBREMENT

Description

EXEMPLES DE PROBLEMES DE DENOMBREMENT

Sujets

• exercice
• exercices
• exercice de

Informations

• Publié par: porthos
• Nombre de lectures: 1 212
• Langue: Français

Extrait


 G -    ˛   - - G -
 " ˛    ˛ 
- ˛ G "
 G - ˛ - ˛
G ˛  EXEMPLES DE PROBLÈMES DE DÉNOMBREMENT Exercice 1 Quelques questions simples et amusantes 1. Existe-t-il un polygone convexe à 1325 diagonales ? Si oui, lequel ? 2. Combien d'anagrammes d'ANAGRAMME ? 3. Combien y a-t-il de nombres palindromes entre 100 et 1000 ? Et entre 1000 et 10000 ? 4. Démontrer que le nombre M de mots (au sens large) sans lettres répétées que l'on peut faire avec un alphabetn de n lettres (n
2) est égal à : M = E[n!e] 1n 5. Combien y a-t-il de surjections de 1, n + 1 sur 1, n ? Exercice 2 Combinaisons avec répétitions - Applications * 0Soient n et p . Par convention, on pose : = 1.n p 1On note, pour p
1, le nombre d'applications croissantes de 1, p dans 1, n . On a donc = n.n n p pDémontrer que pour p
2 : = Cn n+ p 1 p Applications : est le nombre de :n 1. combinaisons de p éléments (éventuellement répétés) choisis parmi n. 2. façons de répartir p objets dans n rangements. n 3. n-uplets de solutions de l'équation p = x + x + ... + x .1 2 n p 4. termes obtenus après développement et réduction, de (a + a + ... + a ) .1 2 n Exercice 3 Formule d'inversion de Pascal - Applications Soient (a ) et (b ) des familles d'éléments d'un anneau commutatif A telles que :i i 0 i n 0 i n p ka = C b p 0, np p k k =0 p p k kDémontrer : b = ( 1) C a p 0, np p k k =0 Applications : * *1. Soient X et Y des ensembles de cardinal n et p respectivement. p p k k n Le nombre de surjections de X sur Y est : S(n, p) = ( 1) C kp k =1 *2. Soit X un ensemble de cardinal n . n k ( 1) Le nombre de dérangements de X est : d = n!n k ! k =0 Théorème des chapeaux : n invités laissent leur chapeau au vestiaire et repartent les uns après les autres en prenant un chapeau au hasard. La probabilité p qu'ils repartent tous avec un chapeau ne leur appartenant pasn 1 tend vers lorsque n tend vers l'infini. e Exemples de problèmes de dénombrement Page 1 G. COSTANTINI
 ¥   ˛  -  -   -      ˛  ˛   
Exercice 4 Nombres de Bell *Soit B le nombre de partitions de 1, n , pour n . Par convention, on pose B = 1.n 0 n * k1. Montrer que pour tout n : B = C Bn+1 n k k=0 n1 k 2. En déduire : B = n e k ! k =0 Exercice 5 Un théorème de scrutin Dans une urne, il y a p bulletins pour le candidat P et q bulletins pour le candidat Q. On suppose p > q. On note N = p + q. Le but de cet exercice est de déterminer la probabilité que, durant tout le dépouillement, P soit toujours en tête. ème1 si le n bulletin dépouillé est pour P Soit x la suite définie par x = ( ) nn 1 n N 1 sinon y = 00 nOn définit la suite y par :( )n 0 n N y = xn k k =1 (y représente le résultat de l'élection après n dépouillements)n On représente la suite (y ) dans un repère par la ligne polygonale joignant les points de coordonnées (n, y ).n n 1. Calculer le nombre de lignes polygonales (correspondantes à des suites ( y ) possibles) joignants lesn n
0 points (0, 0) et (p + q, p q). 2. Combien de ces lignes ne rencontrent pas l'axe des abscisses ? 3. Démontrer que la probabilité que, durant tout le dépouillement, P soit toujours en tête est égale à : p q p + q Exercice 6 Variables aléatoires de Bernoulli non indépendantes * Soient n, p . On dispose de p lots à répartir entre n personnes P , ... , P de la façon suivante : chaque lot est attribué par tirage1 n au sort d'une personne parmi les n. Calculer le nombre moyen de personnes qui ne recevront aucun lot. Exercice 7 Stabilité de la loi binomiale Démontrer le théorème de stabilité de la loi binomiale : Si X B(m ; p) et Y B(n ; p) avec X et Y indépendantes, alors : X + Y B(m + n ; p) Exemples de problèmes de dénombrement Page 2 G. COSTANTINI - 
-
-
 - - ·  ·  -




¥ -  -  -  -  
¥ ¥  - ¥ -  - ¥ -  · ¥ - EXEMPLES DE PROBLÈMES DE DÉNOMBREMENT : SOLUTIONS Exercice 1 Quelques questions simples et amusantes 1. Existe-t-il un polygone convexe à 1325 diagonales ? Si oui, lequel ? 2Il y a C façons de choisir 2 sommets dans un n-gone. On obtient alors soit une diagonale, soit un des n côtés.n Le nombre de diagonales d du n-gone est donc :n n(n 3)2 d = C n = n n 2 L'équation d = 1325 admet une seule solution dans qui est n = 53.n Un polygone à 53 côtés a 1325 diagonales. 2. Combien d'anagrammes d'ANAGRAMME ? Le mot ANAGRAMME a 9 lettres, dont 3 sont des A, 2 sont de M d'où : 9! = 30240 tels anagrammes 3!2! 3. Combien y a-t-il de nombres palindromes entre 100 et 1000 ? Et entre 1000 et 10000 ? De tels nombre palindromes ne peuvent être constitués que deux chiffres. Le premier (celui des centaines, ou celui des milliers pour la deuxième question) ne pouvant être nul. Donc autant de palindromes entre 100 et 1000 qu'entre 1000 et 10000, à savoir : 9 10 = 90. 2. Démontrer que le nombre M de mots (au sens large) sans lettres répétées que l'on peut faire avec un alphabetn de n lettres (n
2) est égal à : M = E[n!e] 1n n n n 1 1 1 1 1pOn a : M = A = n! = n! = n! e = n! e n! n n (n p)! q! q! q! k =1 k =1 q=0 q=n q=n 1 n! 1 1 1 1 Or : 1 < n! = = 1 + < = = 1 + < 2 q 1q! (n + q)! (n +1)...(n + q) n(n +1)q=n q=0 q=1 q=0 1 n +1 En conséquence : 1 < n! e M < 2n D'où : E[n! e] M = 1n M = E[n!e] 1n 3. Combien y a-t-il de surjections de 1, n + 1 sur 1, n ? Notons ƒ une telle surjection. Alors, un et un seul élément y de 1, n admet deux antécédents par ƒ. (Les 1autres n'en ont qu'un seul). La restriction de ƒ à 1, n + 1 \ ƒ ({y}) est alors une bijection sur 1, n \ {y}. ƒ est donc caractérisée par : • le choix de y (n possibilités) 2• le choix des deux antécédents de y dans 1, n + 1 ( C possibilités)n+1 1 • Le choix d'une bijection de 1, n + 1 \ ƒ ({y}) sur 1, n \ {y} ((n 1)! possibilités) n(n +1)!2 Le nombre recherché est donc : n C (n 1)! = n+1 2 Exemples de problèmes de dénombrement Page 3 G. COSTANTINI- - j
˛ ˆ j ˆ
- -

ˆ "
 - - ˛ j ˆ
˛ -  - 
ˆ ˛
j ˛ j j j - j j fi ˛ fi j
j
j - j
j


˛
" - - G - ˛
Exercice 2 Combinaisons avec répétitions - Applications p I. Détermination de pour p



2.n Notons F l'ensemble des applications croissantes de 1, p dans 1, n . I.1. Où l'on associe une application strictement croissante à tout élément de F Soit ƒ F. Considérons l'application g de 1, p dans 1, n + p 1 définie par : g(x) = ƒ(x) + x 1. Montrons que g est strictement croissante : Pour tout x 1, p 1 , on a, d'après la croissance de ƒ : g(x + 1) g(x) = ƒ(x + 1) ƒ(x) + 1 > 0 Donc g est bien strictement croissante sur 1, p . Pour ce qui suit, on note G l'ensemble des applications strictement croissantes de 1, p dans 1, n + p 1 . I.2. Où l'on construit une bijection entre F et G. Considérons l'application : : F G ƒ g : 1, p 1, n + p 1 x ƒ(x) + x 1 I.2.a. Où l'on montre que est injective. Soient ƒ et ƒ telles que (ƒ ) = (ƒ ).1 2 1 2 On a donc, x 1, p : ƒ (x) + x 1 = ƒ (x) + x 1.1 2 D'où, x 1, p : ƒ (x) = ƒ (x), c'est-à-dire ƒ = ƒ .1 2 1 2 L'application est donc injective. I.2.b. Où l'on montre que est surjective. Soit g G. Montrons qu'il existe ƒ dans F telle que (ƒ) = g. Évidemment, l'application ƒ définie par ƒ(x) = g(x) x + 1 est candidate car elle satisfait la condition (ƒ) = g. Mais nous devons, au préalable, nous assurer que cette application ƒ est bien élément de F ! I.2.b.i. Où l'on encadre l'application g Montrons, par récurrence sur x 1, p , la propriété : (x) : x g(x) • On a évidemment 1 g(1) d'où (1). • Montrons que, pour tout x 1, p 1 , on a : (x) (x + 1). Supposons (x), c'est-à-dire x g(x), pour un certain x 1, p 1 . Exemples de problèmes de dénombrement Page 4 G. COSTANTINI˛  " - ˛
"


"


-
˛

- j
G 

 
-



˛ ˆ -
-
- - -  - ˛ - - -
- ˛ -  - - - -

-  ˛ - " -
-

   ˛
- ˛  " -
Comme g est strictement croissante, on peut alors écrire : x g(x) < g(x + 1) Donc : x + 1 g(x + 1) D'où (x + 1). Du principe de récurrence, on déduit : x 1, p : x g(x). Montrons, par récurrence descendante sur x 1, p , la propriété Q(x) : g(x) x + n 1 • On a évidemment g(p) n + p 1 d'où Q(p). • Montrons que, pour tout x 2, p , on a : Q(x) Q(x 1). Supposons Q(x), c'est-à-dire g(x) x + n 1, pour un certain x 2, p . Comme g est strictement croissante, on peut alors écrire : g(x 1) < g(x) x + n 1 Donc : g(x 1) x + n 2 D'où Q(x 1). Du principe de récurrence, on déduit : x 1, p : g(x) x + n 1. Bilan : x 1 ; p : x g(x) x + n 1 I.2.b.ii. Où l'on vérifie que ƒƒ est élément de F.ƒƒ De ce qui précède, on déduit immédiatement (en retranchant x 1) : x 1, p : 1 ƒ(x) n L'application ƒ est donc bien à valeurs dans 1, n . Reste à montrer que ƒ est croissante sur 1, p . x 1, p 1 , ƒ(x + 1) ƒ(x) = g(x + 1) x g(x) + x 1 = g(x + 1) g(x) 1
0 *(car g(x + 1) g(x) ) L'application ƒ est bien croissante sur 1, p Donc est surjective. Il y a donc autant d'application croissantes de 1, p dans 1, n que d'applications strictement croissantes de 1, p dans 1, n + p 1 : p p = Cn n+ p 1 Exemples de problèmes de dénombrement Page 5 G. COSTANTINI G G a  a  a - a
a  a  G  G G  G ˛ G         G  G  - - - - - G pII. Interprétations des nombres n pII.1. est le nombre de combinaisons de p éléments (éventuellement répétés) choisis parmi n.n Soit E un ensemble ordonné de cardinal n. Une combinaison de p éléments (éventuellement répétés) choisis parmi n est un p-uplet (x ; x ; ... ; x ) dont1 2 p les composantes x ; x ; ... ; x sont éléments de E et telles que : x x ... x .1 2 p 1 2 p (On parle aussi de p-uplet "ordonné") Chacun de ces p-uplets ordonnés est caractérisé par une application croissante de 1, p dans E. pIl y a donc p-uplets ordonnés d'éléments de E.n Exemple : • Une urne contient n boules numérotées de 1 à n. On effectue p tirages successifs, avec