Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Activités sur le chapitre 11 - Formules de
dénombrement - Méthodes informatiques

 

Activité1 - Exercices classiques de dénombrement

Certains des énoncés ci-dessous sont inspirés, parfois très directement, du livre "Probabilités fortuites" de Gérard Furgier, paru aux éditions ellipses.

Exercice 1 - Par ici la monnaie

Combien y a-t-il de manières de payer une somme de 45 francs en pièces de 1 et 2 francs? Et en pièces de 1, 2 et 5 francs? Et si l'on remplaçait 45 par 450?

On pourra traiter ce problème par la théorie (penser alors en particulier à la méthode des séries génératrices) ou choisir une approche informatique (et travailler par récurrence).

Exercice 2 - Décompositions...

Combien y a-t-il de manières de choisir 8 entiers positifs tels que leur somme soit égale à 60?

Exercice 2 bis - Décompositions pas nulles

Calculer aussi simplement que possible le nombre de manières de décomposer le nombre 60 en somme de huit entiers tous non nuls...

Exercice 3 - Jeux interdits

Dans une ville où les jeux sont interdits, deux parieurs impénitents ont néanmoins décidé de passer outre et de faire une partie de pile ou face suivant la règle suivante : chacun mise mille francs. On lance la pièce. On compte les ``pile'' et les ``face''. Si trois ``pile'' sortent avant que trois ``face'' ne sortent, le joueur A gagne. Sinon, c'est le joueur B. Après 2 lancers, ``pile'' est sorti deux fois et A commence à se frotter les mains lorsqu'une descente de police intempestive oblige les joueurs à cesser la partie. Comment répartiriez-vous les 2000 francs de mise entre les joueurs en tenant compte de l'état du jeu au moment de son arrêt forcé?

Exercice 4 - Le juge et l'analyste

L'entraîneur d'une équipe de football dispose de 22 joueurs pour former son équipe. Sur ces 22 joueurs, 11 sont vraiment bons : on les appellera dans la suite l'équipe A, et 11 un peu moins : on les appellera l'équipe B. On admettra que les postes sont interchangeables et que tous les joueurs de l'équipe B sont du même niveau.

Le souhait de l'entraîneur serait évidemment d'avoir la meilleure équipe possible et de choisir tous ses joueurs dans l'équipe A. Mais les aléas du sport étant ce qu'ils sont, il doit, avant chaque match, tenir compte du fait qu'un nombre p de joueurs de l'équipe A est soit en garde à vue, soit en audition chez le juge (0 p 11).

1 - Pour une valeur donnée de p, combien y a-t-il de manières pour le juge de choisir les p prochains joueurs à interroger ou à écrouer?

2 - Pour une valeur donnée de p, combien d'équipes différentes l'Olympique de Marseille peut-il être amené à présenter sur le terrain?

3 - En généralisant l'approche et le résultat des deux premières questions à un jeu utilisant des équipes de n joueurs, montrer que

Exercice 5 - Y'a pas que le foot dans la vie

Retrouver le résultat de la dernière question de l'exercice 4 en utilisant l'égalité

(1+x)2n = (1+x)n (1+x)n

Exercice 6 - Le bal de Saint-Péravy la Colombe.

1 - Préambule mathématique : formule d'inversion de Pascal.

Soit (g0, g1, , gn, ) une suite de nombres entiers. On définit, pour n 0,

Montrer que, pour tout n 0,

(raisonner par récurrence sur n, voir le paragraphe {section_fonctions_generatrices} pour une autre méthode).

Au bal des pompiers de Saint-Péravy la Colombe, chaque cavalier vient avec sa soeur. Le bal rassemble n couples, et chaque jeune fille, dans ces régions rurales, danse avec un seul cavalier. Soit Ak un groupe de k danseurs (k n). On désigne par S(Ak) l'ensemble des manières de former les couples, telles que seules les jeunes filles du groupe Ak se retrouvent avec leur frère. Enfin, on désigne par d(p) le nombre de manières d'ordonner l'ensemble {1, 2, , p} de telle sorte qu'aucun nombre ne soit à sa place ``naturelle'' (la première place pour le 1, etc). On appelle de tels ordres des ``dérangements''.

2 - Montrer que Card S(Ak) = d(n-k).

3 - Montrer que l'ensemble R des répartitions possibles en couples est égal à

4 - Calculer, en fonction de k, le nombre ak de groupes Ak possibles (ici, k est fixé).

5 - Exprimer en fonction des ak et des d(n-k) le cardinal de l'ensemble R.

Question 6 - Combien de distributions en couples hétérosexuels non consanguins peut-on former?

Exercice 7 - Le nombre de surjections.

Sur une lointaine planète, il est d'usage que pour chaque hypermarché installé, les propriétaires versent un bakchich à un parti politique. Pour ne pas faire de vague, il est nécessaire que chaque parti touche au moins un dessous de table. Il y a n hypermarchés et p partis politiques. On note Snp le nombre de répartitions possibles des n pots-de-vin entre les p partis.

1 - Montrer que :

Indication - Incendiez l'un des hypermarchés, considérez la répartition des pots-de-vin restants et examinez deux cas : soit cette répartition est encore satisfaisante soit elle ne l'est plus.

2 - Montrer que :

Indication - Considérer toutes les répartitions possibles des bakchichs entre les n partis (satisfaisantes ou non) et stratifier en fonction du nombre de partis arrosés.

3 - Montrer que :

Exercice 8 - Une application de la formule du crible de Poincaré

Montrer que

Indication - Soit E désigne l'ensemble des applications de {1, , m-1} dans {1, , m}. Pour 1 i m, on désigne par Ei l'ensemble des applications de {1, , m-1} dans {1, , m} \ {i}. Vérifier que

et appliquer la formule du crible de Poincaré pour calculer de deux manières différentes le cardinal de E.

Exercice 9 - Une autre application de la formule du crible

Montrer que, si p > n,

Indication - Cette fois E est l'ensemble des p-uplets (x1, , xp) d'entiers positifs ou nuls tels que x1 + + xp = n. On admettra que le membre de gauche est égal au cardinal de E (cf. l'exercice 2). Noter que si p > n, l'égalité x1 + + xp = n n'est possible que si au moins un des xi est nul : en déduire que E est la réunion des Ei (1 i n) où Ei est l'ensemble des p-uplets de E pour lesquels xi = 0. Noter enfin que les Ei s'identifient à des ensembles de (p-1)-uplets de somme n, et que, plus généralement, leurs intersections vérifient une propriété analogue.

Exercice 10 - Applications croissantes entre deux parties de .

1 - Soit k et n deux entiers, avec k n. Montrer que le nombre d'applications strictement croissantes de {1, , k} dans {1, , n} est égal à Cnk.

2 - On ne fait plus l'hypothèse k n. Montrer que le nombre d'applications croissantes au sens large de {1, , k} dans {1, , n} est égal à Cn+k-1k (montrer que l'on définit une correspondance bijective entre l'ensemble formé par ces applications et celui formé par les (k+1)-uplets (x1, , xk+1) k+1 solutions de

en associant à l'application f la solution

et déduire le résultat demandé des conclusions de l'exercice 2.

(On n'oubliera pas d'établir l'injectivité : si les solutions (x1, , xk+1) et (x'1, , x'k+1) associées à des applications f et f ' sont égales, alors f = f ', et la surjectivité : toute solution (x1, , xk+1) est l'image dans cette correspondance d'une certaine application f).

Exercice 11 - Marches aléatoires

Un point du plan à coordonnées entières se déplace de la manière suivante : partant de M0 (m,m'), on peut accéder à M1 et M'1 de coordonnées respectives (m+1,m'+1) et (m+1,m'-1) et à eux seuls. En d'autres termes, on avance à chaque pas d'une unité vers la droite soit en montant d'une unité, soit en descendant d'une unité.

1 - Accessibilité

Soit M et N deux points de coordonnées respectives (m,m') et (n,n'). Montrer que, pour qu'il existe, avec la règle ci-dessus, une marche allant de M à N, il est nécessaire et suffisant que soient satisfaites les conditions suivantes :

(On notera que la première condition pourrait être omise puisqu'elle est résulte de la seconde).

Lorsque ces conditions sont satisfaites, on dira que N est accessible à partir de M.

2 - Lorsque N est accessible à partir de M, compter le nombre de chemins possibles de M vers N. (Remarquer que le nombre de montées est déterminé par m, m', n et n' et que la connaissance d'un chemin équivaut à celle des étapes où il monte).

3 - Principe de réflexion.

Soit M le point de coordonnées (1,0) et M' le point de coordonnées (-1,0) (le symétrique de M par rapport à l'axe des abscisses. Soit N un point du plan accessible à partir de M.

3.1 - On suppose qu'il existe, parmi les chemins reliant M à N, un chemin coupant l'axe des abscisses. Montrer que N est accessible à partir de M'. (Associer au chemin issu de M le nouveau chemin suivant : si P est le premier point où le chemin issu de M rencontre l'axe des abscisses (et éventuellement le seul), on symétrise la partie MP de la trajectoire pour obtenir une trajectoire M'P. Puis on va de P à N suivant la même trajectoire que celle suivie par le chemin initial issu de M).

3.2 - Montrer que la correspondance définie en 3.1. réalise une bijection entre l'ensemble des chemins reliant M à N coupant l'axe des abscisses et l'ensemble de tous les chemins reliant M' à N.

Les résultats de la question 3 constituent le principe de réflexion.

4 - Applications du principe de réflexion.

Soit p et q deux nombres entiers positifs de même parité, avec q p.

4.1 - Montrer que le point N de coordonnées (p+q,p-q) est accessible à partir de l'origine O.

4.2 - Calculer le nombre de chemins allant de O à N, puis le nombre de chemins allant de O à N sans jamais traverser l'axe des abscisses (remarquer que la première étape d'un tel chemin est forcément OM et appliquer les résultats de 3.)

4.3 - Montrer que, parmi les chemins reliant O à N, la proportion de ceux qui ne rencontrent jamais l'axe des abscisses est égale à

(Dénombrer le complémentaire : il se sépare en deux familles disjointes, ceux qui partent vers le bas à la première étape et ceux qui, partent vers le haut mais reviennent couper l'axe des abscisses. Le compte des premiers est simple, celui des seconds repose sur le principe de réflexion).

4.4 - Au second tour d'une élection présidentielle, le vainqueur a obtenu 14 357 602 voix et le perdant 13 568 401 voix. Quelle est la probabilité pour qu'au cours du dépouillement, le candidat élu ait toujours été majoritaire (on admettra que tous les bulletins sont versés dans une même gigantesque urne avant le dépouillement et que les dépouillements sont équiprobables).