Discrete Mathematics — Permutations & Combinations

Contents

1Factorielle easy lab

La factorielle compte le nombre de permutations d'un ensemble à $n$ éléments. Écrire une fonction factorielle(n) qui renvoie $n!$ pour tout entier $n \geq 0$, sans utiliser math.factorial. On rappelle que $0! = 1$.

• Vérifier sur $n = 0, 1, 5, 9, 12$.

2Arrangements $P(n, k)$ easy lab

$P(n, k)$ compte le nombre d'arrangements ordonnés sans répétition de $k$ éléments choisis dans un ensemble à $n$ éléments. Écrire arrangements(n, k) qui renvoie $n(n-1)(n-2)\cdots(n-k+1)$ par produit itératif, sans utiliser math.perm ni math.factorial.

• Conventions : arrangements(n, 0) == 1, arrangements(n, k) == 0 si $k > n$.
• Vérifier : $P(9, 3) = 504$, $P(12, 5) = 95\,040$.

3Coefficient binomial via Pascal medium lab

L'identité de Pascal donne $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, avec $\binom{n}{0} = \binom{n}{n} = 1$. Écrire binomial(n, k) qui calcule $\binom{n}{k}$ en construisant ligne par ligne le triangle de Pascal, sans utiliser math.comb. Renvoyer $0$ si $k < 0$ ou $k > n$.

• Vérifier : $\binom{12}{5} = 792$, $\binom{20}{10} = 184\,756$.
• Vérifier la symétrie $\binom{n}{k} = \binom{n}{n-k}$ pour $n = 20$, $k = 7$.

4Principe des tiroirs & détection de collision medium lab

Si $N$ pigeons sont répartis dans $k$ tiroirs, au moins un tiroir contient au moins $\lceil N/k \rceil$ pigeons.

1. Écrire tiroir_min(N, k) qui renvoie le nombre minimum d'objets dans le tiroir le plus rempli, garanti par le principe des tiroirs généralisé (pour $N = 0$, $k \geq 1$, renvoyer $0$).
2. Écrire a_collision(liste) qui renvoie True si la liste contient au moins un doublon, False sinon.
3. Application : un mot de passe est tiré aléatoirement parmi $26^4 = 456\,976$ possibilités. Combien de personnes faut-il pour qu'au moins deux partagent leur mot de passe (par tiroirs) avec $1\,000\,000$ d'utilisateurs ?

5Choix d'une équipe — binomial easy math

On choisit une équipe de $k = 5$ joueurs parmi un effectif de $n = 12$ personnes.

1. Combien d'équipes différentes peut-on former ?
2. L'effectif contient $4$ Suisses, $5$ Éthiopiens et $3$ Brésiliens. Combien d'équipes de $5$ contiennent exactement $2$ Suisses, $2$ Éthiopiens et $1$ Brésilien ?
3. Si l'ordre comptait (top-$5$ classement), combien d'arrangements ?

6Anagrammes de MISSISSIPPI medium math

Le mot MISSISSIPPI contient 11 lettres : 1 M, 4 I, 4 S et 2 P.

1. Combien d'anagrammes distinctes peut-on former avec ces 11 lettres ?
2. Combien d'anagrammes commencent par M ?
3. Combien d'anagrammes ne contiennent aucun $\mathrm{SS}$ consécutif ? (Question ouverte, indication ci-dessous.)

7Principe des tiroirs — mois de naissance medium math

Un groupe contient $N$ personnes. On range chaque personne dans le tiroir correspondant à son mois de naissance ($k = 12$ tiroirs).

1. D'après le principe des tiroirs généralisé, quel est le nombre minimum garanti de personnes nées le même mois pour $N = 50$ ? pour $N = 100$ ? pour $N = 200$ ?
2. Quel est le plus petit $N$ tel qu'au moins $5$ personnes naissent forcément le même mois ?
3. Démontrer rigoureusement la borne $\lceil N/k \rceil$ (par contradiction).

8Étoiles et barres — distribution de bonbons hard math

On distribue $k = 10$ bonbons identiques entre $n = 4$ enfants (un enfant peut recevoir 0, 1 ou plusieurs bonbons).

1. Combien de distributions possibles ?
2. Combien de distributions si chaque enfant doit recevoir au moins $1$ bonbon ?
3. Combien de distributions si le premier enfant doit recevoir au moins $2$ et le second au moins $3$ ?
4. Combien de solutions de $x_1 + x_2 + x_3 + x_4 = 10$ en entiers $0 \leq x_i \leq 5$ ?