EXEMPLES DE PROBLEMES DE DENOMBREMENT

Publié par

EXEMPLES DE PROBLEMES DE DENOMBREMENT

Publié le : jeudi 21 juillet 2011
Lecture(s) : 1 104
Nombre de pages : 11
Voir plus Voir moins
    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 n0 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 remise, et on considère les numéros obtenus dans leur globalité (sans tenir compte de l'ordre dans lequel ils sont p apparus). Alors, il y a tirages possibles.n pII.2. est le nombre de façons de répartir p objets dans n rangements.n En effet, à chaque répartition de p objets dans n rangements, on fait correspondre bijectivement un code binaire de n + p 1 bits constitué de p bits égaux à 1 (les p objets) et n 1 bits égaux à 0 (les n 1 séparations entre les n rangements). Par exemple, avec p = 9 objets et n = 5 rangements, le code 1110101111100 signifie que l'on a rangé 3 objets dans le premier rangement, 1 objet dans le second, 5 objets dans le troisième et aucun objet dans le quatrième et le cinquième. n 1 p On sait qu'il y a C = C tels codes. D'où le résultat.n+ p 1 n+ p 1 9 Exemple : nombre de façons de ranger 9 chemises dans 5 tiroirs : = 715.5 np II.3. est le nombre de n-uplets de solutions de l'équation p = x + x + ... + x .1 2 nn En effet, décomposer l'entier p en une somme de n entiers, c'est comme répartir p objets dans n rangements ème(chaque x représentant le nombre d'objets présents dans le i rangement)i 3 10 Exemple : nombre de triplets (x ; y , z) solutions de l'équation 10 = x + y + z. Il y en a = 66.3 ppII.4. est le nombre de termes obtenus après développement et réduction, de (a + a + ... + a ) .n 1 2 n 1 2 nEn effet, en développant, on obtient une somme de produits du type a a ...a où + + ... + = p.1 2 n1 2 n On est ainsi ramené au cas II.3. 5 5 Exemple : (a + b + c + d) comportera = 56 termes après développement et réduction.4 Exemples de problèmes de dénombrement Page 6 G. COSTANTINI      ˛    ˛    ˛  "    -  -     -  -  -  -  -  -  -               -                   -  -  -   -      - "                                                                                         ˛      Exercice 3 Formule d'inversion de Pascal - Applications a b0 0 a b p1 1 kNotons A = a et B = b . La relation a = C b p 0, n se traduit alors matriciellement par :n n p2 2 p k k =0 a bn n 1 0 0 0 0 1 1 0 0 0 A = M B avec M = 1 2 1 0 0n n n n 0 0 1 2 n C C C Cn n n n Les matrices M sont triangulaires, de déterminant 1, donc inversibles. En inversant M , on déduira unen n expression des b (0 p n) en fonction des a (0 p n). Or, d'après la formule du binôme de Newton, on ap p 1 1 0 0 0 0 1 1+ X 1 1 0 0 0 X 2 2 (1+ X ) = 1 2 1 0 0 X 0 n 0 1 2 n n (1+ X ) C C C C Xn n n n 1 1 X 1+ X 2 1 2 On a donc : X = M (1+ X )n n n X (1+ X ) 1 p 2 nPour déterminer M , on décompose X (0 p n) dans la base (1, (1 + X), (1 + X) , ..., (1 + X) ) :n Pour cela, il suffit d'écrire : p p p k p k k X = (1 + X 1) = C ( 1) (1 + X )p k =0 1 0 0 0 0 1 1 0 0 0 1 D'où : M = 1 2 1 0 0n 0 n 0 n 1 1 n 2 2 n ( 1) C ( 1) C ( 1) C Cn n n n En conséquence : p p k kb = ( 1) C a p 0, np p k k =0 Application 1 : nombre de surjections d'un ensemble de cardinal n sur un ensemble de cardinal p. * * Soit X un ensemble de cardinal n et Y un ensemble de cardinal p . On note S(n, p) le nombre de surjections de X sur Y. Recherchons une expression de S(n, p). Pour cela, dénombrons de deux façons différentes le nombre d'applications ƒ de X dans Y. Exemples de problèmes de dénombrement Page 7 G. COSTANTINI  - -  - -   - -  -  -    - - - -      -   -  - ˛  - - Soit ƒ une application de X dans Y. • Pour chacun des n éléments de X, nous pouvons associer l'un des p éléments de Y. D'après le principe n multiplicatif, nous avons donc p façons de construire ƒ. • Nous pouvons dénombrer différemment : on sait que ƒ définit une surjection de X sur ƒ(X). Notons k le k cardinal de ƒ(X). On a donc : 1 k p. Nous avons C façons de choisir les k éléments de ƒ(X) parmi les pp éléments de Y. Et, avec nos notations, nous avons S(n, k) façons de choisir une surjection de X dans un ensemble de cardinal k. En sommant, pour 1 k p, on obtient : p kC S(n, k) applications de X dans Y.p k =1 Bilan : p n k p = C S(n, k)p k =1 D'après la formule d'inversion de Pascal, on déduit : p p k k n S(n, p) = ( 1) C kp k =1 *Application 2 : nombre de dérangements d d'un ensemble X de cardinal n . (Est appelé dérangement de Xn toute bijection de X n'ayant aucun point fixe) Soit B (X) l'ensemble des bijections de X ayant k points fixes (pour 0 k n)k n kOn a : Card(B (X)) = C dk n kn n kEn effet, une bijection de X ayant k points fixes dérange n k éléments de X. Or, il y a C façons de choisir lesn n k éléments dérangés et d dérangements de l'ensemble de ces n k éléments.n k En sommant, pour k = 0 à n : nn n n k kCard(B (X )) = C d = C dk n n k n k k =0k =0 k =0 n En outre, Card(B (X )) = n!k k =0 n k On a donc : n! = C dn k k =0 Et d'après la formule d'inversion de Pascal : n n nn k k( 1) ( 1)k n kd = C ( 1) k ! = n! = n!n n (n k)! k ! k =0 k =0 k =0 Ce résultat a pour conséquence un curieux théorème dit "des chapeaux" (d'autres versions existent) : n invités laissent leur chapeau au vestiaire et repartent en prenant un chapeau au hasard. La probabilité p qu'ilsn repartent tous avec un chapeau ne leur appartenant pas est : Exemples de problèmes de dénombrement Page 8 G. COSTANTINI    - - -  - " - - - p - ¥ -  -  - ¥  - ¥ p   ¥    ¥ fi     ¥   ˛   ¥   ·  - ˛ -  p ¥ ˛   ˛ - fi ˛ ¾ - ¾ ¾ n k d ( 1)np = = n n! k ! k =0 3 Par exemple, p = . (On peut retrouver ce résultat à l'aide d'un arbre)4 8 1 Et lorsque n tend vers l'infini, p tend vers .n e Exercice 4 Nombres de Bell *Soit B le nombre de partitions de 1, n , pour n . Par convention, on pose B = 1.n 0 1. Considérons une partition de 1, n + 1 . Notons la partie contenant l'élément n + 1 et q son cardinal (q 1, n + 1 ) q 1 Il y a C façons de choisir les q 1 éléments (autres que n + 1) dans la partie .n Le complémentaire de contient n + 1 q éléments et il y a B façons de le partitionner.n+1 q n+1 n q 1 k On a donc : B = C B = C Bn+1 n n+1 q n k q=1 k=0 nk 2. Remarquons, tout d'abord, que la série de est bien convergente d'après le test de D'Alembert : k ! k =0 nn(k +1) k ! 1 1*k , = 1+ 0 n k(k +1)! k +1 kk n 1 k Posons, pour tout n : S = n e k ! k =0 On a : S = 1 = B et pour tout n :0 0 n n k n n n+1 1 p 1 1 1 (1+ p) 1 ( p +1)k k kkC S = C = C p = = = Sn+1n k n n e p! e p! e p! e ( p +1)! k =0 k =0 p=0 p=0 k =0 p=0 p=0 Les suites (B ) et (S ) sont initialisées par la même constante et vérifient la même relation de récurrence.n n n1 k Elle sont donc égales : B = n e k ! k =0 Exercice 5 Un théorème de scrutin p p1. Autant que de N-listes de { 1 ; 1} contenant p fois l'élément 1, soit : C = C .N p+q 2. Pour construire une telle ligne, on doit nécessairement avoir : y = x = 1.1 1 Le nombre total de lignes entre (1, 1) et (p + q, p q) est le même qu'entre (0, 0) et (p + q 1, p q 1), p 1soit, d'après la question 1 : C .p+q 1 Reste à compter les lignes ne rencontrent pas l'axe des abscisses entre (1, 1) et (p + q, p q). Exemples de problèmes de dénombrement Page 9 G. COSTANTINI  - - - - · - - ˛ „ - - - ˙ - -  - - · - - - -  ˙ W  W - ˛ ˙ -  -  -  - - - - -  - - -  -  -  - Comptons celles qui rencontrent l'axe. D'après le principe de réflexion, il y en a autant que de lignes allant de p (1, 1) à (p + q, p q), soit autant que de (0, 0) à (p + q 1, p q + 1), soit Cp+q 1 Le nombre de lignes entre (0, 0) et (N, p q) qui ne recontrent pas l'axe est donc égal à : ( p + q 1)! ( p + q 1)! ( p + q 1)! p qp 1 p pC C = = p q = C( )p+q 1 p+q 1 p+q ( p 1)!q! p!(q 1)! p!q! p + q 3. D'après les questions précédentes, la probabilité recherchée est : nombre de lignes ne rencontrant pas l'axe p q = nombre de lignes total 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. pL'univers de cette expérience aléatoire est l'ensemble des p-listes de {P ; ... ; P }. Il y en a n .1 n Pour tout k 1, n , notons E l'événement décrit par "la personne P ne reçoit aucun lot". L'événement E estk k k p constitué des p-listes de {P ; ... ; P } \ {P }. Il y en a (n 1) .1 n k p(n 1) En choisissant la probabilité uniforme P sur , on a : P(E ) = .k pn 1 si E est réalisék Notons X = k 0 sinon p(n 1) Les X , 1 k n, sont des variables aléatoires de loi de Bernoulli de paramètre .k pn n Posons X = X = nombre de personnes ne recevant aucun lot.i i=1 p(n 1) On a : E(X) = nE(X ) = 1 p 1n 44 256 Exemple : si p = 4 et n = 5, E(X) = = > 2. Le nombre de personnes ne recevant aucun lot, en moyenne, 3 1255 est supérieur à 2. Remarque : dans cet exercice , les X , 1 k n, sont non indépendantes (lorsque n  2) :k En effet, soient h et k distincts compris entre 1 et n. E E est constitué des p-listes de {P ; ... ; P } \ {P ; P }.k h 1 n k h p p p(n 2) (n 1) (n 1)pIl y en a (n 2) . Donc P(E E ) = ; et comme P(E ).P(E ) = , on en déduit que :k h k hp p pn nn 1 1 1 1P( X (1) X (1) ) P( X (1) ) P( X (1) )k h k h Donc X et X ne sont pas indépendantes et les X , 1 k n, non plus.k h k Exemples de problèmes de dénombrement Page 10 G. COSTANTINI
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.