🇫🇷 France 🇲🇦 Maroc
Accueil › Terminale Spé › Combinatoire et dénombrement
IV Probabilités & dénombrement · Chapitre 01 / 17

Combinatoire et dénombrement

Arrangements, combinaisons, coefficients binomiaux.

15 min de lecture
6 sections, 14 exemples
40 exercices · 4 problèmes

Conforme au programme officiel 2025-2026 · mis à jour le · notre méthode de vérification

L'essentiel en 30 secondes

Le dénombrement compte sans lister. Le principe multiplicatif enchaîne les choix indépendants ; les k-uplets comptent les listes avec répétition, les arrangements les listes sans répétition, et les combinaisons les choix non ordonnés. Le coefficient binomial « k parmi n » compte les parties à k éléments d'un ensemble à n éléments et se calcule avec le triangle de Pascal.

1 I. Principes fondamentaux

1. Principe additif

2. Principe multiplicatif

Démonstration via le produit cartésien
Le produit cartésien de deux ensembles AA et BB est :

A×B={(a,b)∣a∈A et b∈B}A \times B = \{(a, b) \mid a \in A \text{ et } b \in B\}

Chaque élément de AA peut être associé à chaque élément de BB, ce qui donne :

card(A×B)=card(A)×card(B)\text{card}(A \times B) = \text{card}(A) \times \text{card}(B)

3. Inclusion-exclusion

Démonstration
On décompose A∪BA \cup B en trois parties disjointes :

• A∖BA \setminus B : éléments dans AA mais pas dans BB
• A∩BA \cap B : éléments dans AA et dans BB
• B∖AB \setminus A : éléments dans BB mais pas dans AA

Donc card(A∪B)=card(A∖B)+card(A∩B)+card(B∖A)\text{card}(A \cup B) = \text{card}(A \setminus B) + \text{card}(A \cap B) + \text{card}(B \setminus A).

Or card(A)=card(A∖B)+card(A∩B)\text{card}(A) = \text{card}(A \setminus B) + \text{card}(A \cap B) et card(B)=card(B∖A)+card(A∩B)\text{card}(B) = \text{card}(B \setminus A) + \text{card}(A \cap B).

En substituant : card(A∪B)=card(A)+card(B)−card(A∩B)\text{card}(A \cup B) = \text{card}(A) + \text{card}(B) - \text{card}(A \cap B).

2 II. pp-listes (pp-uplets)

1. pp-listes avec répétition

Démonstration
Par le principe multiplicatif : pour chaque position du pp-uplet, on a nn choix possibles. Les choix sont indépendants.

Donc le nombre total est n×n×⋯×n⏟p fois=np\underbrace{n \times n \times \cdots \times n}_{p \text{ fois}} = n^p.

2. pp-listes sans répétition (arrangements)

Démonstration
Par le principe multiplicatif :

• 1ère position : nn choix
• 2ème position : n−1n - 1 choix (un élément déjà utilisé)
• 3ème position : n−2n - 2 choix
• ⋮\vdots
• pp-ème position : n−p+1n - p + 1 choix

Donc Anp=n(n−1)(n−2)⋯(n−p+1)=n!(n−p)!A_n^p = n(n-1)(n-2)\cdots(n-p+1) = \dfrac{n!}{(n-p)!}.

3 III. Permutations

Démonstration
C'est le cas p=np = n de la formule des arrangements :

Ann=n!(n−n)!=n!0!=n!1=n!A_n^n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!

4 IV. Combinaisons

1. Définition et formule

Démonstration
Chaque combinaison de pp éléments peut être ordonnée de p!p! façons, donnant ainsi un arrangement.

Donc : nombre d'arrangements == nombre de combinaisons ×\times p!p!

Anp=(np)×p!A_n^p = \binom{n}{p} \times p!

D'où :

(np)=Anpp!=n!p! (n−p)!\binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p!\,(n-p)!}

2. Propriétés des coefficients binomiaux

Démonstration de la symétrie
(nn−p)=n!(n−p)! [n−(n−p)]!=n!(n−p)! p!=(np)\binom{n}{n-p} = \frac{n!}{(n-p)!\,[n-(n-p)]!} = \frac{n!}{(n-p)!\,p!} = \binom{n}{p}

Interprétation : Choisir pp éléments à prendre parmi nn, c'est la même chose que choisir n−pn - p éléments à laisser.

3. Triangle de Pascal

Démonstration combinatoire
On fixe un élément aa dans l'ensemble EE à nn éléments. Les combinaisons de pp éléments parmi nn se répartissent en deux catégories disjointes :

• Celles qui contiennent aa : il reste à choisir p−1p - 1 éléments parmi les n−1n - 1 restants → (n−1p−1)\binom{n-1}{p-1}
• Celles qui ne contiennent pas aa : il faut choisir pp éléments parmi les n−1n - 1 restants → (n−1p)\binom{n-1}{p}

Par le principe additif : (np)=(n−1p−1)+(n−1p)\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}.

Triangle de Pascal (lignes n=0n = 0 à n=6n = 6) :

n=0n = 0 : 1\qquad\qquad\qquad\qquad 1
n=1n = 1 :   11\qquad\qquad\qquad\; 1 \qquad 1
n=2n = 2 : 121\qquad\qquad\quad 1 \qquad 2 \qquad 1
n=3n = 3 : 1331\qquad\qquad 1 \qquad 3 \qquad 3 \qquad 1
n=4n = 4 :   14641\qquad\; 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1
n=5n = 5 : 15101051\quad 1 \qquad 5 \quad 10 \quad 10 \qquad 5 \qquad 1
n=6n = 6 : 16152015611 \qquad 6 \quad 15 \quad 20 \quad 15 \qquad 6 \qquad 1

Chaque nombre est la somme des deux nombres situés au-dessus de lui.

4. Binôme de Newton

Idée de la démonstration
On développe le produit (a+b)n=(a+b)(a+b)⋯(a+b)⏟n facteurs(a + b)^n = \underbrace{(a+b)(a+b)\cdots(a+b)}_{n \text{ facteurs}}.

Dans chaque facteur, on choisit aa ou bb. Un terme an−kbka^{n-k}b^k apparaît chaque fois qu'on choisit bb exactement kk fois parmi les nn facteurs.

Le nombre de façons de choisir ces kk facteurs est (nk)\binom{n}{k}.

5 V. Méthodes et stratégies de dénombrement

1. Schéma de décision

Arbre de decision — Quel outil de denombrement utiliser ?
L'ordre compte-t-il ?
Non
(np)\displaystyle\binom{n}{p}
Combinaison
Oui
Repetitions possibles ?
Oui
npn^p
p-liste
Non
Tous les elements ?
Oui
n!n!
Permutation
Non
n!(n−p)!\dfrac{n!}{(n-p)!}
Arrangement

2. Passer par le complémentaire

3. Décomposer en étapes

4. Distinguer des cas

5. Fixer un élément

6. Placer d'abord les contraintes

6 Tableau récapitulatif

SituationOrdreRépétitionFormule
pp-liste avec répétitionOuiOuinpn^p
ArrangementOuiNonn!(n−p)!\dfrac{n!}{(n-p)!}
PermutationOuiNonn!n!
CombinaisonNonNon(np)=n!p!(n−p)!\binom{n}{p} = \dfrac{n!}{p!(n-p)!}
Anagrammes (avec rép.)Oui—n!r1!×r2!×⋯×rk!\dfrac{n!}{r_1! \times r_2! \times \cdots \times r_k!}

Ce chapitre est tombé au bac

8 sujets officiels de bac comportent un exercice sur ce chapitre — chaque corrigé est détaillé question par question.

2025 Nouvelle-Calédonie · Jour 2 2025 Nouvelle-Calédonie · Jour 1 2025 Amérique du Sud · Jour 2 2025 Amérique du Sud · Jour 1 2025 Métropole · Septembre Jour 1 2025 Polynésie · Septembre 2025 Polynésie · Jour 1 2025 Centres étrangers · Jour 2

Questions fréquentes

Quelle est la différence entre une combinaison et un arrangement ?
Dans un arrangement, l'ordre des éléments compte ; dans une combinaison, non. Choisir 3 délégués parmi 20 est une combinaison ((203)\binom{20}{3}) ; choisir un président, un trésorier et un secrétaire est un arrangement. Le réflexe : demandez-vous si échanger deux éléments change le résultat.
Quand utiliser une factorielle et quand utiliser un coefficient binomial ?
La factorielle n!n! compte les permutations, c'est-à-dire toutes les façons d'ordonner nn éléments distincts. Le coefficient binomial (nk)\binom{n}{k} compte les parties à kk éléments d'un ensemble à nn éléments, sans tenir compte de l'ordre.
Comment calculer un coefficient binomial sans calculatrice ?
On utilise (nk)=n!k! (n−k)!\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}, en simplifiant avant de multiplier. Par exemple (103)=10×9×83×2×1=120\binom{10}{3} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120. Pensez aussi à la symétrie (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}, qui évite souvent les gros calculs.

1. Formules essentielles

Principes fondamentaux

Les 4 configurations

Propriétés de (np)\binom{n}{p}

Triangle de Pascal (lignes n=0n = 0 à n=6n = 6) :

n=0n = 0 : 1\qquad\qquad\qquad\qquad 1
n=1n = 1 :   11\qquad\qquad\qquad\; 1 \qquad 1
n=2n = 2 : 121\qquad\qquad\quad 1 \qquad 2 \qquad 1
n=3n = 3 : 1331\qquad\qquad 1 \qquad 3 \qquad 3 \qquad 1
n=4n = 4 :   14641\qquad\; 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1
n=5n = 5 : 15101051\quad 1 \qquad 5 \quad 10 \quad 10 \qquad 5 \qquad 1
n=6n = 6 : 16152015611 \qquad 6 \quad 15 \quad 20 \quad 15 \qquad 6 \qquad 1

Binôme de Newton

2. Schéma de décision

Arbre de decision — Quel outil de denombrement utiliser ?
L'ordre compte-t-il ?
Non
(np)\displaystyle\binom{n}{p}
Combinaison
Oui
Repetitions possibles ?
Oui
npn^p
p-liste
Non
Tous les elements ?
Oui
n!n!
Permutation
Non
n!(n−p)!\dfrac{n!}{(n-p)!}
Arrangement

3. Les 3 questions à se poser

4. Les 6 méthodes

5. Tableau récapitulatif

SituationOrdreRépétitionFormule
pp-liste avec rép.OuiOuinpn^p
ArrangementOuiNonn!(n−p)!\dfrac{n!}{(n-p)!}
PermutationOuiNonn!n!
CombinaisonNonNon(np)=n!p!(n−p)!\binom{n}{p} = \dfrac{n!}{p!(n-p)!}
Anagrammes (rép.)Oui—n!r1!×⋯×rk!\dfrac{n!}{r_1! \times \cdots \times r_k!}
40 exercices disponibles
Exercice 1
Facile
Un code PIN est composé de 4 chiffres choisis parmi {0,1,2,…,9}\{0, 1, 2, \ldots, 9\}. Les répétitions sont autorisées.
1.
Combien de codes PIN peut-on former ?
Chaque position du code offre 10 choix (les chiffres de 0 à 9), et les répétitions sont autorisées. C'est une **4-liste avec répétition** d'un ensemble à 10 éléments. D'après le principe multiplicatif : $10 \times 10 \times 10 \times 10 = 10^4 = \boxed{10\,000}$
2.
Combien de codes PIN ont leurs 4 chiffres tous distincts ?
On cherche le nombre de **4-listes sans répétition** (arrangements) de 4 chiffres parmi 10 : $A_{10}^4 = 10 \times 9 \times 8 \times 7 = \boxed{5\,040}$ En effet, le 1er chiffre a 10 choix, le 2e a 9 (un chiffre déjà pris), le 3e a 8, le 4e a 7.
3.
Combien de codes PIN commencent par un chiffre non nul ?
Le premier chiffre est choisi parmi $\{1, 2, \ldots, 9\}$ : **9 choix**. Les 3 chiffres suivants sont choisis librement parmi $\{0, 1, \ldots, 9\}$ : **10 choix** chacun. Par le principe multiplicatif : $9 \times 10 \times 10 \times 10 = 9 \times 10^3 = \boxed{9\,000}$
Exercice 2
Facile
Un restaurant propose 4 entrées, 5 plats principaux et 3 desserts.
1.
Combien de menus complets (entrée + plat + dessert) peut-on composer ?
Un menu complet se compose de 3 choix successifs indépendants. Par le **principe multiplicatif** : $4 \times 5 \times 3 = \boxed{60}$ On peut former 60 menus complets.
2.
Combien de menus si le dessert est optionnel (on peut ne pas en prendre) ?
Si le dessert est optionnel, on a **4 choix** pour le dessert : les 3 desserts ou « pas de dessert ». Nombre de menus : $4 \times 5 \times (3 + 1) = 4 \times 5 \times 4 = \boxed{80}$
3.
Combien de menus si 2 plats sont indisponibles ?
Il reste $5 - 2 = 3$ plats disponibles. Le nombre de menus complets est : $4 \times 3 \times 3 = \boxed{36}$
Exercice 3
Facile
Calculer les combinaisons suivantes.
1.
Calculer (73)\binom{7}{3} en utilisant la formule (nk)=n!k!(n−k)!\binom{n}{k} = \dfrac{n!}{k!(n-k)!}.
On applique la formule : $\binom{7}{3} = \dfrac{7!}{3! \times 4!} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = \dfrac{210}{6} = \boxed{35}$
2.
Calculer (107)\binom{10}{7} en utilisant la propriété de symétrie (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}.
Par la propriété de symétrie : $\binom{10}{7} = \binom{10}{10-7} = \binom{10}{3} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = \dfrac{720}{6} = \boxed{120}$ Cette propriété permet de simplifier le calcul en choisissant le plus petit entre $k$ et $n-k$.
3.
Calculer (80)+(81)+(88)\binom{8}{0} + \binom{8}{1} + \binom{8}{8}.
On utilise les cas particuliers connus : $\binom{8}{0} = 1 \quad ; \quad \binom{8}{1} = 8 \quad ; \quad \binom{8}{8} = 1$ Donc : $\binom{8}{0} + \binom{8}{1} + \binom{8}{8} = 1 + 8 + 1 = \boxed{10}$
Exercice 4
Facile
On considère le mot MARDI (5 lettres toutes distinctes).
1.
Combien d'anagrammes peut-on former avec les lettres de MARDI ?
Le mot MARDI comporte 5 lettres **toutes distinctes**. Le nombre d'anagrammes est le nombre de **permutations** de 5 éléments : $5! = 5 \times 4 \times 3 \times 2 \times 1 = \boxed{120}$
2.
Combien d'anagrammes commencent par la lettre M ?
Si M est fixé en première position, il reste 4 lettres (A, R, D, I) à permuter dans les 4 positions restantes : $4! = 4 \times 3 \times 2 \times 1 = \boxed{24}$
3.
Combien d'anagrammes commencent par une voyelle ?
Les voyelles de MARDI sont A et I, soit **2 choix** pour la première lettre. Pour chacun de ces choix, les 4 lettres restantes se permutent librement : $4!$ possibilités. Par le principe multiplicatif : $2 \times 4! = 2 \times 24 = \boxed{48}$
Exercice 5
Facile
On lance un dé équilibré à 6 faces trois fois de suite.
1.
Combien de résultats possibles y a-t-il ?
Chaque lancer a 6 issues possibles. Les lancers sont indépendants. C'est une **3-liste avec répétition** de $\{1, 2, 3, 4, 5, 6\}$. $6^3 = \boxed{216}$
2.
Combien de résultats ne contiennent que des faces paires ?
Les faces paires sont $\{2, 4, 6\}$, soit 3 choix par lancer. $3^3 = \boxed{27}$
3.
Combien de résultats contiennent au moins un 6 ?
On utilise le **dénombrement par complémentaire**. Nombre de résultats **sans aucun 6** : chaque lancer a 5 choix $\{1,2,3,4,5\}$, soit $5^3 = 125$. Nombre de résultats avec **au moins un 6** : $6^3 - 5^3 = 216 - 125 = \boxed{91}$
Exercice 6
Facile
Dans une classe de 32 élèves, 20 pratiquent l'anglais et 18 l'espagnol. Seulement 4 élèves ne pratiquent aucune de ces deux langues.
1.
Combien d'élèves pratiquent au moins une des deux langues ?
Si 4 élèves ne pratiquent aucune langue, alors le nombre d'élèves qui pratiquent **au moins une** langue est : $32 - 4 = \boxed{28}$
2.
En utilisant la formule d'inclusion-exclusion, déterminer le nombre d'élèves qui pratiquent les deux langues.
Notons $A$ l'ensemble des élèves qui font anglais et $E$ ceux qui font espagnol. Par la formule d'inclusion-exclusion : $\text{card}(A \cup E) = \text{card}(A) + \text{card}(E) - \text{card}(A \cap E)$ $28 = 20 + 18 - \text{card}(A \cap E)$ $\text{card}(A \cap E) = 20 + 18 - 28 = \boxed{10}$ 10 élèves pratiquent les deux langues.
3.
Combien d'élèves pratiquent exactement une seule langue ?
Nombre d'élèves qui pratiquent **uniquement l'anglais** : $20 - 10 = 10$. Nombre d'élèves qui pratiquent **uniquement l'espagnol** : $18 - 10 = 8$. Nombre d'élèves qui pratiquent **exactement une** langue : $10 + 8 = \boxed{18}$ **Vérification :** $10 + 8 + 10 + 4 = 32$ ✓ (une seule langue + deux langues + aucune).
Exercice 7
Facile
Soit E={1,2,3,4,5,6}E = \{1, 2, 3, 4, 5, 6\}.
1.
Combien EE possède-t-il de sous-ensembles ?
Le nombre de sous-ensembles (ou **parties**) d'un ensemble à $n$ éléments est $2^n$. Ici $n = 6$, donc : $2^6 = \boxed{64}$ (Cela inclut l'ensemble vide $\varnothing$ et $E$ lui-même.)
2.
Combien de sous-ensembles à 2 éléments EE possède-t-il ?
On choisit 2 éléments parmi 6 **sans ordre** : c'est une combinaison. $\binom{6}{2} = \dfrac{6!}{2! \times 4!} = \dfrac{6 \times 5}{2} = \boxed{15}$
3.
Combien de sous-ensembles contiennent au moins 4 éléments ?
Les sous-ensembles d'au moins 4 éléments sont ceux de taille 4, 5 ou 6 : $\binom{6}{4} + \binom{6}{5} + \binom{6}{6} = 15 + 6 + 1 = \boxed{22}$ On a utilisé $\binom{6}{4} = \binom{6}{2} = 15$ et $\binom{6}{5} = \binom{6}{1} = 6$.
Exercice 8
Facile
On s'intéresse au triangle de Pascal.
1.
Écrire la ligne n=5n = 5 du triangle de Pascal.
La ligne $n = 5$ contient les coefficients $\binom{5}{k}$ pour $k = 0, 1, \ldots, 5$ : $\binom{5}{0} = 1 \;; \; \binom{5}{1} = 5 \;; \; \binom{5}{2} = 10 \;; \; \binom{5}{3} = 10 \;; \; \binom{5}{4} = 5 \;; \; \binom{5}{5} = 1$ La ligne $n=5$ est donc : $\boxed{1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1}$
2.
Vérifier que (52)+(53)=(63)\binom{5}{2} + \binom{5}{3} = \binom{6}{3}.
D'après la ligne calculée : $\binom{5}{2} + \binom{5}{3} = 10 + 10 = 20$ Calculons $\binom{6}{3}$ : $\binom{6}{3} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = \dfrac{120}{6} = 20$ On vérifie bien $\binom{5}{2} + \binom{5}{3} = \binom{6}{3} = 20$ ✓. C'est la **formule de Pascal** : $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$.
3.
Calculer la somme des coefficients de la ligne n=5n = 5.
La somme des coefficients de la ligne $n$ du triangle de Pascal vaut $2^n$. Vérifions : $1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5 \quad ✓$ Ce résultat découle de la formule du binôme avec $a = b = 1$ : $\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$
Exercice 9
Facile
Les plaques d'immatriculation sont composées de 2 lettres (parmi 26) suivies de 3 chiffres (parmi 10).
1.
Combien de plaques peut-on former (répétitions autorisées) ?
Par le principe multiplicatif : $26 \times 26 \times 10 \times 10 \times 10 = 26^2 \times 10^3 = 676 \times 1\,000 = \boxed{676\,000}$
2.
Combien de plaques ont leurs 3 chiffres tous distincts ?
Les 2 lettres sont libres : $26^2$ choix. Les 3 chiffres doivent être distincts : c'est un arrangement de 3 parmi 10, soit $10 \times 9 \times 8 = 720$. $26^2 \times 720 = 676 \times 720 = \boxed{486\,720}$
3.
Combien de plaques commencent par AB ?
Les 2 lettres sont fixées (A puis B) : **1 seul choix**. Les 3 chiffres sont libres : $10^3 = 1\,000$ choix. $1 \times 1\,000 = \boxed{1\,000}$
Exercice 10
Facile
On tire simultanément 3 cartes d'un jeu de 32 cartes.
1.
Combien de tirages de 3 cartes peut-on effectuer ?
On tire 3 cartes **simultanément** (donc sans ordre et sans répétition). C'est une combinaison : $\binom{32}{3} = \dfrac{32 \times 31 \times 30}{3!} = \dfrac{29\,760}{6} = \boxed{4\,960}$
2.
Combien de tirages contiennent exactement 3 cœurs ?
Un jeu de 32 cartes contient 8 cœurs. On choisit 3 cœurs parmi 8 : $\binom{8}{3} = \dfrac{8 \times 7 \times 6}{6} = \boxed{56}$
3.
Combien de tirages ne contiennent aucun as ?
Un jeu de 32 cartes contient 4 as. Les cartes « non-as » sont $32 - 4 = 28$. On choisit 3 cartes parmi ces 28 : $\binom{28}{3} = \dfrac{28 \times 27 \times 26}{6} = \dfrac{19\,656}{6} = \boxed{3\,276}$
Exercice 11
Intermédiaire
On considère les anagrammes du mot CLASSE (6 lettres dont S apparaît 2 fois).
1.
Combien d'anagrammes peut-on former ?
Le mot CLASSE comporte 6 lettres : C, L, A, S, S, E avec la lettre S répétée 2 fois. Le nombre d'anagrammes est : $\dfrac{6!}{2!} = \dfrac{720}{2} = \boxed{360}$ On divise par $2!$ car les deux S sont indiscernables.
2.
Combien d'anagrammes commencent par la lettre C ?
Si C est fixé en 1ère position, il reste 5 lettres (L, A, S, S, E) avec S répété 2 fois : $\dfrac{5!}{2!} = \dfrac{120}{2} = \boxed{60}$
3.
Combien d'anagrammes ont les deux S consécutifs ?
On regroupe les deux S en un **bloc [SS]**. On obtient 5 « objets » à permuter : C, L, A, [SS], E, tous distincts. $5! = \boxed{120}$
4.
Combien d'anagrammes commencent par CL ?
Si C est en position 1 et L en position 2, il reste 4 lettres (A, S, S, E) à permuter : $\dfrac{4!}{2!} = \dfrac{24}{2} = \boxed{12}$
Exercice 12
Intermédiaire
On considère une grille rectangulaire de 4 colonnes et 3 lignes. On se déplace du coin bas-gauche (0,0)(0,0) au coin haut-droit (4,3)(4,3) en ne faisant que des pas vers la droite (D) ou vers le haut (H).
1.
Combien de chemins mènent de (0,0)(0,0) à (4,3)(4,3) ?
Chaque chemin est composé de **4 pas D** et **3 pas H**, soit 7 pas au total. Un chemin est entièrement déterminé par le choix des positions des 3 pas H parmi les 7 : $\binom{7}{3} = \dfrac{7 \times 6 \times 5}{3!} = \dfrac{210}{6} = \boxed{35}$
2.
Combien de chemins passent par le point (2,1)(2,1) ?
Un chemin passant par $(2,1)$ se décompose en : - Un chemin de $(0,0)$ à $(2,1)$ : $\binom{3}{1} = 3$ chemins (3 pas dont 1 H) - Un chemin de $(2,1)$ à $(4,3)$ : $\binom{4}{2} = 6$ chemins (4 pas dont 2 H) Par le principe multiplicatif : $3 \times 6 = \boxed{18}$
3.
Combien de chemins ne passent PAS par (2,1)(2,1) ?
Par dénombrement du complémentaire : Nombre de chemins ne passant pas par $(2,1)$ = nombre total $-$ nombre passant par $(2,1)$ : $35 - 18 = \boxed{17}$
Exercice 13
Intermédiaire
Un groupe est composé de 8 hommes et 6 femmes. On forme un comité de 5 personnes.
1.
Combien de comités peut-on former ?
On choisit 5 personnes parmi $8 + 6 = 14$ : $\binom{14}{5} = \dfrac{14 \times 13 \times 12 \times 11 \times 10}{5!} = \dfrac{240\,240}{120} = \boxed{2\,002}$
2.
Combien de comités contiennent exactement 2 femmes ?
On choisit 2 femmes parmi 6 **et** 3 hommes parmi 8 : $\binom{6}{2} \times \binom{8}{3} = 15 \times 56 = \boxed{840}$
3.
Combien de comités contiennent au moins une femme ?
Par le **complémentaire**, on retire les comités sans aucune femme (5 hommes parmi 8) : $\binom{14}{5} - \binom{8}{5} = 2\,002 - 56 = \boxed{1\,946}$
4.
Combien de comités contiennent plus de femmes que d'hommes ?
Pour que les femmes soient majoritaires dans un comité de 5, il faut au moins 3 femmes. **3 femmes et 2 hommes :** $\binom{6}{3} \times \binom{8}{2} = 20 \times 28 = 560$ **4 femmes et 1 homme :** $\binom{6}{4} \times \binom{8}{1} = 15 \times 8 = 120$ **5 femmes :** $\binom{6}{5} \times \binom{8}{0} = 6 \times 1 = 6$ Total : $560 + 120 + 6 = \boxed{686}$
Exercice 14
Intermédiaire
On utilise la formule du binôme de Newton pour développer (2x−1)4(2x - 1)^4.
1.
Rappeler la formule du binôme de Newton.
Pour tous réels $a, b$ et tout entier $n \geq 0$ : $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
2.
Développer (2x−1)4(2x - 1)^4.
On pose $a = 2x$ et $b = -1$, $n = 4$ : $(2x-1)^4 = \sum_{k=0}^{4} \binom{4}{k} (2x)^{4-k}(-1)^k$ $= \binom{4}{0}(2x)^4 - \binom{4}{1}(2x)^3 + \binom{4}{2}(2x)^2 - \binom{4}{3}(2x) + \binom{4}{4}$ $= 16x^4 - 4 \times 8x^3 + 6 \times 4x^2 - 4 \times 2x + 1$ $= \boxed{16x^4 - 32x^3 + 24x^2 - 8x + 1}$
3.
Quel est le coefficient de x2x^2 dans ce développement ?
D'après le développement, le terme en $x^2$ est $24x^2$. Le coefficient de $x^2$ est donc $\boxed{24}$. On pouvait le calculer directement : $\binom{4}{2}(2)^2(-1)^2 = 6 \times 4 \times 1 = 24$.
4.
En posant x=10x = 10, calculer 19419^4.
On a $(2 \times 10 - 1)^4 = 19^4$. En remplaçant $x$ par 10 dans le développement : $19^4 = 16 \times 10^4 - 32 \times 10^3 + 24 \times 10^2 - 8 \times 10 + 1$ $= 160\,000 - 32\,000 + 2\,400 - 80 + 1 = \boxed{130\,321}$
Exercice 15
Intermédiaire
On tire simultanément 5 cartes d'un jeu de 52 cartes.
1.
Combien de mains de 5 cartes peut-on former ?
$\binom{52}{5} = \dfrac{52 \times 51 \times 50 \times 49 \times 48}{5!} = \dfrac{311\,875\,200}{120} = \boxed{2\,598\,960}$
2.
Combien de mains contiennent exactement 2 as ?
On choisit 2 as parmi 4, puis 3 cartes non-as parmi 48 : $\binom{4}{2} \times \binom{48}{3} = 6 \times 17\,296 = \boxed{103\,776}$ Où $\binom{48}{3} = \dfrac{48 \times 47 \times 46}{6} = 17\,296$.
3.
Combien de mains contiennent les 4 as ?
Les 4 as sont dans la main. Il reste à choisir 1 carte parmi les 48 restantes : $\binom{4}{4} \times \binom{48}{1} = 1 \times 48 = \boxed{48}$
4.
Combien de mains ne contiennent aucun as ?
On choisit 5 cartes parmi les 48 cartes qui ne sont pas des as : $\binom{48}{5} = \dfrac{48 \times 47 \times 46 \times 45 \times 44}{120} = \boxed{1\,712\,304}$ **Vérification :** on peut vérifier que la somme des mains avec 0, 1, 2, 3 ou 4 as donne bien $\binom{52}{5}$.
Exercice 16
Intermédiaire
Un mot de passe est composé de 6 caractères choisis parmi les 26 lettres minuscules et les 10 chiffres (36 caractères au total).
1.
Combien de mots de passe peut-on former ?
C'est une 6-liste avec répétition d'un ensemble à 36 éléments : $36^6 = \boxed{2\,176\,782\,336}$ Soit environ $2{,}18$ milliards de mots de passe.
2.
Combien de mots de passe ne contiennent que des lettres (aucun chiffre) ?
On n'utilise que les 26 lettres : $26^6 = \boxed{308\,915\,776}$
3.
En déduire le nombre de mots de passe contenant au moins un chiffre.
Par **dénombrement du complémentaire** : Mots de passe avec au moins un chiffre = Total $-$ mots de passe sans aucun chiffre : $36^6 - 26^6 = 2\,176\,782\,336 - 308\,915\,776 = \boxed{1\,867\,866\,560}$
Exercice 17
Intermédiaire
Montrer que ∑k=0n(nk)=2n\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n en utilisant la formule du binôme de Newton.
Correction détaillée
D'après la formule du binôme de Newton, pour tous réels $a$ et $b$ : $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$ Posons $a = 1$ et $b = 1$ : $(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} \times 1^{n-k} \times 1^k = \sum_{k=0}^{n} \binom{n}{k}$ Donc : $\boxed{\sum_{k=0}^{n} \binom{n}{k} = 2^n}$ **Interprétation combinatoire :** Le membre de gauche compte tous les sous-ensembles d'un ensemble à $n$ éléments (classés par taille $k$). Le membre de droite les compte directement (chaque élément est soit pris, soit non).
Exercice 18
Intermédiaire
Lors d'une conférence, 12 personnes se rencontrent et chacune serre la main de toutes les autres.
1.
Combien de poignées de mains sont échangées ?
Une poignée de mains correspond à un choix non ordonné de 2 personnes parmi 12 : $\binom{12}{2} = \dfrac{12 \times 11}{2} = \boxed{66}$
2.
Si les 12 personnes se répartissent en 2 groupes de 6, combien de poignées de mains se font entre personnes de groupes différents ?
Chaque personne du groupe 1 serre la main de chaque personne du groupe 2 : $6 \times 6 = \boxed{36}$ poignées de mains inter-groupes.
3.
En déduire le nombre de poignées de mains intra-groupes (au sein du même groupe).
Le nombre total de poignées de mains est 66. Les poignées inter-groupes sont 36. Poignées intra-groupes : $66 - 36 = 30$. **Vérification :** Chaque groupe de 6 échange $\binom{6}{2} = 15$ poignées. Deux groupes : $2 \times 15 = 30$ ✓. $\boxed{30}$
Exercice 19
Intermédiaire
On choisit 3 livres parmi 10 livres différents.
1.
De combien de façons peut-on distribuer ces 3 livres comme 1er, 2e et 3e prix ?
L'ordre compte (1er prix ≠ 2e prix). C'est un **arrangement** de 3 parmi 10 : $A_{10}^3 = 10 \times 9 \times 8 = \boxed{720}$
2.
De combien de façons peut-on simplement choisir 3 livres (sans distinction de prix) ?
L'ordre ne compte pas. C'est une **combinaison** : $\binom{10}{3} = \dfrac{10 \times 9 \times 8}{3!} = \dfrac{720}{6} = \boxed{120}$
3.
Vérifier la relation Anp=p!×(np)A_n^p = p! \times \binom{n}{p} sur cet exemple.
On a $A_{10}^3 = 720$ et $\binom{10}{3} = 120$. Vérifions : $3! \times \binom{10}{3} = 6 \times 120 = 720 = A_{10}^3$ ✓. **Explication :** pour passer d'une combinaison à un arrangement, on ordonne les $p$ éléments choisis, ce qui donne $p!$ possibilités supplémentaires.
Exercice 20
Intermédiaire
Un code binaire est un mot de longueur 5 composé de 0 et de 1.
1.
Combien de codes binaires de longueur 5 existe-t-il ?
Chaque position a 2 choix (0 ou 1). C'est une 5-liste avec répétition de $\{0,1\}$ : $2^5 = \boxed{32}$
2.
Combien de codes contiennent exactement 3 fois le chiffre 1 ?
On choisit les 3 positions (parmi 5) qui contiendront un 1 : $\binom{5}{3} = 10$ Il y a $\boxed{10}$ codes avec exactement trois 1.
3.
Combien de codes contiennent au plus 2 fois le chiffre 1 ?
On additionne les codes avec 0, 1 ou 2 fois le chiffre 1 : $\binom{5}{0} + \binom{5}{1} + \binom{5}{2} = 1 + 5 + 10 = \boxed{16}$ **Remarque :** c'est exactement la moitié de 32. En effet, par symétrie du triangle de Pascal, les codes avec au plus 2 uns sont en bijection avec les codes avec au moins 3 uns.
Exercice 21
Difficile
On considère les anagrammes du mot BANANE (6 lettres : B, A, N, A, N, E).
1.
Combien d'anagrammes peut-on former ?
Le mot BANANE contient 6 lettres avec les répétitions : A apparaît 2 fois et N apparaît 2 fois. $\dfrac{6!}{2! \times 2!} = \dfrac{720}{4} = \boxed{180}$
2.
Combien d'anagrammes commencent par B et finissent par E ?
B est fixé en position 1, E en position 6. Il reste 4 lettres (A, N, A, N) à permuter, avec A×2 et N×2 : $\dfrac{4!}{2! \times 2!} = \dfrac{24}{4} = \boxed{6}$
3.
Combien d'anagrammes ont les deux A consécutifs ?
On regroupe les deux A en un bloc [AA]. On obtient 5 objets à permuter : B, [AA], N, N, E avec N répété 2 fois. $\dfrac{5!}{2!} = \dfrac{120}{2} = \boxed{60}$
4.
Combien d'anagrammes ont les deux A NON consécutifs ?
Par le complémentaire : Anagrammes avec A non consécutifs = Total $-$ anagrammes avec A consécutifs : $180 - 60 = \boxed{120}$
Exercice 22
Difficile
Six personnes s'installent autour d'une table ronde.
1.
Combien de dispositions différentes y a-t-il ?
Pour des **permutations circulaires** de $n$ personnes, on fixe une personne pour éliminer les rotations identiques. Nombre de dispositions : $(6-1)! = 5! = \boxed{120}$
2.
Combien de dispositions si deux personnes A et B doivent être voisines ?
On regroupe A et B en un **bloc**. On obtient 5 « objets » à placer en cercle : $(5-1)! = 4! = 24$. Mais à l'intérieur du bloc, A et B peuvent être dans 2 ordres (AB ou BA). $4! \times 2 = 24 \times 2 = \boxed{48}$
3.
Combien de dispositions si A et B ne doivent PAS être voisins ?
Par complémentaire : $5! - 4! \times 2 = 120 - 48 = \boxed{72}$
4.
Parmi les 6 personnes, 3 sont des femmes (F) et 3 des hommes (H). Combien de dispositions alternent hommes et femmes ?
Fixons la position d'une femme (pour éliminer les rotations). Les 2 autres femmes se placent dans les 2 sièges « femmes » restants : $2!$ façons. Les 3 hommes se placent dans les 3 sièges « hommes » : $3!$ façons. $2! \times 3! = 2 \times 6 = \boxed{12}$
Exercice 23
Difficile
Formule de Pascal : (np)=(n−1p−1)+(n−1p)\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p} pour 1≤p≤n−11 \leq p \leq n-1.
1.
Démontrer cette formule en utilisant l'expression factorielle de (np)\binom{n}{p}.
Calculons $\binom{n-1}{p-1} + \binom{n-1}{p}$ : $\dfrac{(n-1)!}{(p-1)!(n-p)!} + \dfrac{(n-1)!}{p!(n-1-p)!}$ Factorisons par $\dfrac{(n-1)!}{p!(n-p)!}$ : $= \dfrac{(n-1)!}{p!(n-p)!} \times p + \dfrac{(n-1)!}{p!(n-p)!} \times (n-p)$ $= \dfrac{(n-1)!}{p!(n-p)!} \times (p + n - p) = \dfrac{(n-1)! \times n}{p!(n-p)!} = \dfrac{n!}{p!(n-p)!} = \binom{n}{p}$
2.
Donner une démonstration combinatoire de cette formule.
Soit $E$ un ensemble à $n$ éléments. Fixons un élément $a \in E$. Les parties de $E$ à $p$ éléments se répartissent en deux catégories **disjointes** : - Celles qui **contiennent** $a$ : on choisit les $p-1$ éléments restants parmi les $n-1$ autres → $\binom{n-1}{p-1}$ - Celles qui **ne contiennent pas** $a$ : on choisit les $p$ éléments parmi les $n-1$ autres → $\binom{n-1}{p}$ Donc $\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}$.
3.
En utilisant cette formule, calculer (2018)\binom{20}{18} rapidement.
Par symétrie : $\binom{20}{18} = \binom{20}{2}$. $\binom{20}{2} = \dfrac{20 \times 19}{2} = \boxed{190}$ **Alternative avec Pascal :** $\binom{20}{18} = \binom{19}{17} + \binom{19}{18} = \binom{19}{2} + 19 = 171 + 19 = 190$ ✓.
4.
En déduire par récurrence que (np)\binom{n}{p} est un entier naturel pour tous 0≤p≤n0 \leq p \leq n.
**Initialisation :** $\binom{n}{0} = 1$ et $\binom{n}{n} = 1$ sont des entiers pour tout $n$. **Récurrence sur $n$ :** Supposons que tous les $\binom{n-1}{k}$ sont des entiers ($0 \leq k \leq n-1$). Pour $1 \leq p \leq n-1$ : $\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}$, qui est une **somme de deux entiers** (par hypothèse de récurrence), donc un entier. **Conclusion :** Par récurrence, $\binom{n}{p} \in \mathbb{N}$ pour tous $0 \leq p \leq n$. (Ce résultat n'est pas évident a priori car $\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$ est un quotient de factorielles.)
Exercice 24
Difficile
Une urne contient 5 boules rouges, 4 boules bleues et 3 boules vertes. On tire simultanément 5 boules.
1.
Combien de tirages de 5 boules peut-on effectuer ?
On choisit 5 boules parmi $5 + 4 + 3 = 12$ : $\binom{12}{5} = \dfrac{12 \times 11 \times 10 \times 9 \times 8}{5!} = \dfrac{95\,040}{120} = \boxed{792}$
2.
Combien de tirages contiennent exactement 2 rouges et 1 verte ?
On choisit 2 rouges parmi 5, 1 verte parmi 3, et les 2 restantes parmi les 4 bleues : $\binom{5}{2} \times \binom{3}{1} \times \binom{4}{2} = 10 \times 3 \times 6 = \boxed{180}$
3.
Combien de tirages contiennent au moins une boule de chaque couleur ?
Par le complémentaire, on retire les tirages où **au moins une couleur est absente**. Notation : $A$ = pas de rouge, $B$ = pas de bleu, $C$ = pas de vert. $|A| = \binom{7}{5} = 21$ (5 parmi les 4B+3V) $|B| = \binom{8}{5} = 56$ (5 parmi les 5R+3V) $|C| = \binom{9}{5} = 126$ (5 parmi les 5R+4B) $|A \cap B| = \binom{3}{5} = 0$ (impossible : seulement 3 vertes) $|A \cap C| = \binom{4}{5} = 0$ (impossible : seulement 4 bleues) $|B \cap C| = \binom{5}{5} = 1$ (les 5 rouges) $|A \cap B \cap C| = 0$ Par inclusion-exclusion : $|A \cup B \cup C| = 21 + 56 + 126 - 0 - 0 - 1 + 0 = 202$. Tirages avec au moins une de chaque couleur : $792 - 202 = \boxed{590}$
4.
Combien de tirages contiennent 5 boules de la même couleur ?
- 5 rouges parmi 5 : $\binom{5}{5} = 1$ - 5 bleues parmi 4 : $\binom{4}{5} = 0$ (impossible) - 5 vertes parmi 3 : $\binom{3}{5} = 0$ (impossible) Total : $\boxed{1}$ seul tirage (les 5 boules rouges).
Exercice 25
Difficile
Un QCM comporte 10 questions. Chaque question propose 4 réponses dont une seule est correcte.
1.
De combien de façons peut-on remplir le QCM en répondant à toutes les questions ?
Chaque question offre 4 choix, et les choix sont indépendants. C'est une 10-liste de $\{A,B,C,D\}$ : $4^{10} = \boxed{1\,048\,576}$
2.
De combien de façons peut-on remplir le QCM si on a le droit de ne pas répondre à certaines questions ?
Chaque question offre 5 choix : A, B, C, D, ou ne pas répondre. $5^{10} = \boxed{9\,765\,625}$
3.
Combien de grilles contiennent exactement 7 bonnes réponses ?
On choisit les 7 questions où la réponse est correcte : $\binom{10}{7}$ façons. Pour les 3 questions restantes, on choisit une mauvaise réponse parmi 3 possibles. $\binom{10}{7} \times 3^3 = 120 \times 27 = \boxed{3\,240}$
4.
Combien de grilles contiennent au moins 8 bonnes réponses ?
On additionne les cas 8, 9 et 10 bonnes réponses : **8 bonnes :** $\binom{10}{8} \times 3^2 = 45 \times 9 = 405$ **9 bonnes :** $\binom{10}{9} \times 3^1 = 10 \times 3 = 30$ **10 bonnes :** $\binom{10}{10} \times 3^0 = 1$ Total : $405 + 30 + 1 = \boxed{436}$
Exercice 26
Difficile
Montrer l'identité : k(nk)=n(n−1k−1)k \binom{n}{k} = n \binom{n-1}{k-1} pour 1≤k≤n1 \leq k \leq n.
1.
Démontrer cette identité par le calcul factoriel.
Calculons le membre de gauche : $k \binom{n}{k} = k \times \dfrac{n!}{k!(n-k)!} = \dfrac{n!}{(k-1)!(n-k)!}$ Calculons le membre de droite : $n \binom{n-1}{k-1} = n \times \dfrac{(n-1)!}{(k-1)!(n-k)!} = \dfrac{n \times (n-1)!}{(k-1)!(n-k)!} = \dfrac{n!}{(k-1)!(n-k)!}$ Les deux expressions sont égales. $\square$
2.
En déduire la valeur de ∑k=0nk(nk)\displaystyle\sum_{k=0}^{n} k \binom{n}{k}.
Le terme $k=0$ est nul. Pour $k \geq 1$, on utilise l'identité : $\sum_{k=1}^{n} k \binom{n}{k} = \sum_{k=1}^{n} n \binom{n-1}{k-1} = n \sum_{k=1}^{n} \binom{n-1}{k-1}$ Par le changement d'indice $j = k-1$ : $= n \sum_{j=0}^{n-1} \binom{n-1}{j} = n \times 2^{n-1}$ Donc : $\boxed{\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}}$
3.
Application : calculer ∑k=010k(10k)\displaystyle\sum_{k=0}^{10} k \binom{10}{k}.
On applique directement la formule : $\sum_{k=0}^{10} k \binom{10}{k} = 10 \times 2^9 = 10 \times 512 = \boxed{5\,120}$
Exercice 27
Difficile
On distribue un jeu de 32 cartes à 4 joueurs, chacun recevant 8 cartes.
1.
De combien de façons peut-on distribuer les 32 cartes à 4 joueurs ?
On choisit 8 cartes pour le joueur 1 parmi 32, puis 8 pour le joueur 2 parmi 24, etc. : $\binom{32}{8} \times \binom{24}{8} \times \binom{16}{8} \times \binom{8}{8} = \dfrac{32!}{(8!)^4}$ Ce nombre est appelé coefficient **multinomial**. $\boxed{\dfrac{32!}{(8!)^4}}$
2.
Combien de mains de 8 cartes le joueur 1 peut-il recevoir ?
$\binom{32}{8} = \dfrac{32!}{8! \times 24!} = \boxed{10\,518\,300}$
3.
Combien de distributions donnent les 4 as au joueur 1 ?
Le joueur 1 a les 4 as + 4 cartes parmi les 28 restantes : $\binom{28}{4}$ choix. Puis les 28 cartes restantes sont distribuées aux 3 autres joueurs : $\dfrac{28!}{(8!)^3} \div \binom{28}{4}$... Plus simplement : on fixe les 4 as chez J1, on choisit 4 cartes parmi 28 pour compléter sa main, puis on distribue le reste : $\binom{28}{4} \times \binom{24}{8} \times \binom{16}{8} \times \binom{8}{8} = \binom{28}{4} \times \dfrac{24!}{(8!)^3}$ $= \boxed{20\,475 \times \dfrac{24!}{(8!)^3}}$
Exercice 28
Difficile
On utilise la formule du binôme de Newton.
1.
Déterminer le coefficient de x3x^3 dans le développement de (1+x)8(1+x)^8.
Le terme général de $(1+x)^8$ est $\binom{8}{k}x^k$. Pour $k = 3$ : le coefficient est $\binom{8}{3} = \dfrac{8 \times 7 \times 6}{6} = \boxed{56}$.
2.
Déterminer le coefficient de x4x^4 dans (1−2x)6(1 - 2x)^6.
Le terme général de $(1-2x)^6$ est $\binom{6}{k}(1)^{6-k}(-2x)^k = \binom{6}{k}(-2)^k x^k$. Pour $k = 4$ : $\binom{6}{4}(-2)^4 = 15 \times 16 = \boxed{240}$
3.
Calculer la somme des coefficients du développement de (3x+2)5(3x + 2)^5.
La **somme des coefficients** d'un polynôme $P(x)$ est $P(1)$. $(3 \times 1 + 2)^5 = 5^5 = \boxed{3\,125}$
4.
Déterminer nn tel que (n3)=84\binom{n}{3} = 84.
On résout $\binom{n}{3} = 84$ : $\dfrac{n(n-1)(n-2)}{6} = 84 \implies n(n-1)(n-2) = 504$ On teste : $8 \times 7 \times 6 = 336$ (trop petit), $9 \times 8 \times 7 = 504$ ✓. Donc $\boxed{n = 9}$.
Exercice 29
Difficile
Dénombrement par complémentaire.
1.
Combien de mots de 5 lettres (parmi 26) contiennent au moins une voyelle ?
Total de mots de 5 lettres : $26^5 = 11\,881\,376$. Mots sans aucune voyelle (21 consonnes) : $21^5 = 4\,084\,101$. Mots avec au moins une voyelle : $26^5 - 21^5 = 11\,881\,376 - 4\,084\,101 = \boxed{7\,797\,275}$
2.
Combien d'entiers de 1 à 1000 ne sont divisibles ni par 3, ni par 5 ?
Notons $A$ = multiples de 3 et $B$ = multiples de 5 dans $\{1, \ldots, 1000\}$. $|A| = \lfloor 1000/3 \rfloor = 333$ $|B| = \lfloor 1000/5 \rfloor = 200$ $|A \cap B| = \lfloor 1000/15 \rfloor = 66$ (multiples de 15) Par inclusion-exclusion : $|A \cup B| = 333 + 200 - 66 = 467$. Entiers divisibles ni par 3 ni par 5 : $1000 - 467 = \boxed{533}$
3.
Combien d'entiers de 1 à 999 contiennent au moins un chiffre 7 dans leur écriture ?
Considérons les entiers de 000 à 999 (en écrivant sur 3 chiffres, avec des zéros non significatifs). Entiers **sans aucun 7** : chaque chiffre a 9 choix (0-9 sauf 7), soit $9^3 = 729$. Entiers avec au moins un 7 parmi $\{000, \ldots, 999\}$ : $1000 - 729 = 271$. Mais 000 n'est pas dans $\{1, \ldots, 999\}$ et ne contient pas de 7. Donc le résultat est le même pour $\{1, \ldots, 999\}$ : $\boxed{271}$
Exercice 30
Difficile
Soit E={1,2,3,…,n}E = \{1, 2, 3, \ldots, n\} avec n≥2n \geq 2.
1.
Dénombrer les paires {a,b}\{a, b\} d'éléments de EE avec a<ba < b.
C'est le nombre de combinaisons de 2 éléments parmi $n$ : $\binom{n}{2} = \dfrac{n(n-1)}{2}$
2.
Dénombrer les triplets (a,b,c)(a, b, c) d'éléments de EE avec a<b<ca < b < c.
C'est le nombre de combinaisons de 3 éléments parmi $n$ (un choix de 3 éléments détermine un unique triplet ordonné) : $\binom{n}{3} = \dfrac{n(n-1)(n-2)}{6}$
3.
Montrer que le nombre de sous-ensembles de EE de taille paire est égal au nombre de sous-ensembles de taille impaire.
On utilise le binôme avec $a = 1, b = -1$ : $(1-1)^n = \sum_{k=0}^{n} \binom{n}{k}(-1)^k = 0$ Donc $\displaystyle\sum_{k \text{ pair}} \binom{n}{k} - \sum_{k \text{ impair}} \binom{n}{k} = 0$. Ainsi $\displaystyle\sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k}$. Comme leur somme vaut $2^n$, chacune vaut $\boxed{2^{n-1}}$.
Exercice 31
Avancé
Un tournoi de tennis rassemble 8 joueurs en élimination directe (quarts de finale, demi-finales, finale).
1.
De combien de façons peut-on constituer le tableau des quarts de finale (4 matchs) ?
Le tableau consiste à répartir les 8 joueurs en 4 paires ordonnées par position dans le tableau. On choisit l'ordre des 8 joueurs : $8!$ permutations. Mais au sein de chaque match, l'ordre des 2 joueurs n'importe pas ($2^4$ symétries), et l'ordre des matchs au sein d'une même moitié de tableau non plus. Plus simplement : on choisit 2 joueurs parmi 8 pour le match 1 : $\binom{8}{2}$, puis 2 parmi 6 pour le match 2 : $\binom{6}{2}$, etc. $\binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2} = 28 \times 15 \times 6 \times 1 = \dfrac{8!}{2^4} = 2\,520$ Si l'ordre des matchs dans le tableau compte (positions fixes) : $\boxed{2\,520}$
2.
Combien de parcours différents (séquences de résultats) le tournoi peut-il avoir ?
À chaque match, un des 2 joueurs gagne. Il y a $4 + 2 + 1 = 7$ matchs au total. Pour un tableau fixé, le nombre de parcours est : $2^7 = \boxed{128}$
3.
De combien de façons peut-on désigner un vainqueur, un finaliste et deux demi-finalistes ?
- Choix du vainqueur : 8 - Choix du finaliste (battu en finale) : 7 - Choix des 2 demi-finalistes (battus en demi) : $\binom{6}{2} = 15$ $8 \times 7 \times 15 = \boxed{840}$
4.
Si les joueurs sont classés de 1 (meilleur) à 8 et que le meilleur gagne toujours, qui remporte le tournoi ? Montrer que le joueur classé 2 n'est pas nécessairement finaliste.
Le joueur 1 gagne tous ses matchs et remporte le tournoi. Le joueur 2 n'est pas nécessairement finaliste : si les joueurs 1 et 2 sont dans la **même moitié de tableau**, ils se rencontrent en demi-finale, et le joueur 2 est éliminé avant la finale. Par exemple, avec le tableau [1 vs 2, 3 vs 4 | 5 vs 6, 7 vs 8] : le joueur 1 bat 2 en quart, puis bat 3 ou 4 en demi, et affronte le vainqueur de l'autre moitié en finale. Le joueur 2 est éliminé dès le premier tour. Le finaliste serait le meilleur joueur de **l'autre moitié** du tableau.
Exercice 32
Avancé
On considère l'identité de Vandermonde : (m+np)=∑k=0p(mk)(np−k)\displaystyle\binom{m+n}{p} = \sum_{k=0}^{p} \binom{m}{k} \binom{n}{p-k}.
1.
Donner une interprétation combinatoire de cette identité.
Considérons un ensemble $E$ de $m+n$ éléments, partitionné en un groupe $A$ de $m$ éléments et un groupe $B$ de $n$ éléments. Le membre de gauche $\binom{m+n}{p}$ compte les parties de $E$ à $p$ éléments. Pour former une telle partie, on choisit $k$ éléments dans $A$ et $p-k$ éléments dans $B$ (avec $0 \leq k \leq p$). Le nombre de choix est $\binom{m}{k}\binom{n}{p-k}$. En sommant sur toutes les valeurs possibles de $k$, on obtient le membre de droite. Cette partition en cas disjoints prouve l'identité. $\square$
2.
En posant m=nm = n et p=np = n, montrer que ∑k=0n(nk)2=(2nn)\displaystyle\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}.
En appliquant Vandermonde avec $m = n$ et $p = n$ : $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$ Or $\binom{n}{n-k} = \binom{n}{k}$ par symétrie. Donc : $\boxed{\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}}$
3.
Application : calculer (50)2+(51)2+(52)2+(53)2+(54)2+(55)2\binom{5}{0}^2 + \binom{5}{1}^2 + \binom{5}{2}^2 + \binom{5}{3}^2 + \binom{5}{4}^2 + \binom{5}{5}^2.
D'après la formule précédente avec $n = 5$ : $\sum_{k=0}^{5} \binom{5}{k}^2 = \binom{10}{5} = 252$ **Vérification :** $1 + 25 + 100 + 100 + 25 + 1 = \boxed{252}$ ✓.
4.
Vérifier l'identité de Vandermonde pour m=3m = 3, n=4n = 4, p=3p = 3.
Membre de gauche : $\binom{7}{3} = 35$. Membre de droite : $\binom{3}{0}\binom{4}{3} + \binom{3}{1}\binom{4}{2} + \binom{3}{2}\binom{4}{1} + \binom{3}{3}\binom{4}{0}$ $= 1 \times 4 + 3 \times 6 + 3 \times 4 + 1 \times 1 = 4 + 18 + 12 + 1 = 35 \quad ✓$
Exercice 33
Avancé
On répartit 12 élèves en 3 groupes.
1.
Si les groupes sont numérotés (G1, G2, G3) et contiennent chacun 4 élèves, combien de répartitions y a-t-il ?
On choisit 4 élèves parmi 12 pour G1, puis 4 parmi 8 pour G2, puis les 4 restants forment G3 : $\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = \boxed{34\,650}$ On reconnaît le coefficient multinomial $\dfrac{12!}{4! \times 4! \times 4!} = 34\,650$.
2.
Si les groupes sont indistinguables (non numérotés), combien de répartitions y a-t-il ?
Si les groupes sont identiques, chaque répartition a été comptée $3! = 6$ fois (une pour chaque permutation des 3 groupes) dans le calcul précédent. $\dfrac{34\,650}{3!} = \dfrac{34\,650}{6} = \boxed{5\,775}$
3.
Combien de répartitions en un groupe de 3, un groupe de 4 et un groupe de 5 (groupes numérotés) ?
On choisit 3 élèves parmi 12 pour le groupe de 3, puis 4 parmi 9 pour le groupe de 4, puis les 5 restants : $\binom{12}{3} \times \binom{9}{4} \times \binom{5}{5} = 220 \times 126 \times 1 = \boxed{27\,720}$
4.
Combien de répartitions en un groupe de 3, un groupe de 3 et un groupe de 6 (groupes non numérotés) ?
Groupes numérotés : $\binom{12}{3} \times \binom{9}{3} \times \binom{6}{6} = 220 \times 84 \times 1 = 18\,480$. Les deux groupes de 3 sont indistinguables, donc on divise par $2!$ : $\dfrac{18\,480}{2} = \boxed{9\,240}$ (On ne divise que par $2!$ et non $3!$ car seuls les deux groupes de même taille sont interchangeables.)
Exercice 34
Avancé
On étudie les propriétés de la formule du binôme de Newton.
1.
Écrire (1+x)n(1+x)^n sous forme de somme.
D'après la formule du binôme de Newton : $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n$
2.
En posant x=−1x = -1, montrer que ∑k=0n(−1)k(nk)=0\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0.
$(1+(-1))^n = 0^n = 0$ pour $n \geq 1$. Or $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$. Avec $x = -1$ : $0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^k$ $\boxed{\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0}$ Ce qui s'écrit aussi : $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n} = 0$.
3.
En déduire que ∑k=0 k pairn(nk)=∑k=0 k impairn(nk)=2n−1\displaystyle\sum_{\substack{k=0 \ k \text{ pair}}}^{n} \binom{n}{k} = \sum_{\substack{k=0 \ k \text{ impair}}}^{n} \binom{n}{k} = 2^{n-1}.
D'après la question 2 : $\sum_{k \text{ pair}} \binom{n}{k} - \sum_{k \text{ impair}} \binom{n}{k} = 0$. Donc $\sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k}$. Or leur somme vaut $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. Donc chacune vaut $\dfrac{2^n}{2} = \boxed{2^{n-1}}$.
4.
En posant x=2x = 2, calculer ∑k=0n(nk)2k\displaystyle\sum_{k=0}^{n} \binom{n}{k} 2^k.
$(1+2)^n = 3^n$. Or $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$. Avec $x = 2$ : $\boxed{\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n}$ Application numérique pour $n = 5$ : $\binom{5}{0} + 2\binom{5}{1} + 4\binom{5}{2} + 8\binom{5}{3} + 16\binom{5}{4} + 32\binom{5}{5} = 1 + 10 + 40 + 80 + 80 + 32 = 243 = 3^5$ ✓.
5.
Calculer ∑k=063k(6k)\displaystyle\sum_{k=0}^{6} 3^k \binom{6}{k}.
D'après la question précédente avec $x = 3$ et $n = 6$ : $\sum_{k=0}^{6} 3^k \binom{6}{k} = (1+3)^6 = 4^6 = \boxed{4\,096}$
Exercice 35
Avancé
On étudie les chemins sur une grille n×nn \times n de (0,0)(0,0) à (n,n)(n,n).
1.
Rappeler le nombre de chemins de (0,0)(0,0) à (n,n)(n,n) (en se déplaçant uniquement vers la droite ou vers le haut).
Chaque chemin est composé de $n$ pas à droite (D) et $n$ pas en haut (H), soit $2n$ pas au total. Le nombre de chemins est : $\binom{2n}{n}$
2.
Application numérique pour n=4n = 4.
$\binom{8}{4} = \dfrac{8 \times 7 \times 6 \times 5}{4!} = \dfrac{1680}{24} = \boxed{70}$
3.
Combien de chemins de (0,0)(0,0) à (4,4)(4,4) passent par le point (2,2)(2,2) ?
Un tel chemin se décompose en : - Un chemin de $(0,0)$ à $(2,2)$ : $\binom{4}{2} = 6$ - Un chemin de $(2,2)$ à $(4,4)$ : $\binom{4}{2} = 6$ Par le principe multiplicatif : $6 \times 6 = \boxed{36}$
4.
Combien de chemins de (0,0)(0,0) à (4,4)(4,4) passent par (1,2)(1,2) puis par (3,3)(3,3) ?
Le chemin se décompose en 3 étapes : - $(0,0) \to (1,2)$ : $\binom{3}{2} = 3$ (3 pas : 1D + 2H) - $(1,2) \to (3,3)$ : $\binom{3}{1} = 3$ (3 pas : 2D + 1H) - $(3,3) \to (4,4)$ : $\binom{2}{1} = 2$ (2 pas : 1D + 1H) Total : $3 \times 3 \times 2 = \boxed{18}$
Exercice 36
Avancé
Une loterie demande de choisir 6 numéros parmi les entiers de 1 à 49. Un tirage de 6 numéros est effectué au hasard.
1.
Combien de grilles de loto peut-on remplir ?
C'est le nombre de combinaisons de 6 parmi 49 : $\binom{49}{6} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{720} = \boxed{13\,983\,816}$
2.
Combien de grilles ont exactement 3 numéros en commun avec le tirage ?
On choisit 3 bons numéros parmi 6, et 3 mauvais parmi les $49 - 6 = 43$ restants : $\binom{6}{3} \times \binom{43}{3} = 20 \times 12\,341 = \boxed{246\,820}$ Où $\binom{43}{3} = \dfrac{43 \times 42 \times 41}{6} = 12\,341$.
3.
Quelle est la probabilité de trouver les 6 bons numéros ?
Il n'y a qu'une seule grille gagnante : $P = \dfrac{1}{\binom{49}{6}} = \dfrac{1}{13\,983\,816} \approx \boxed{7{,}15 \times 10^{-8}}$ Soit environ 1 chance sur 14 millions.
4.
Quelle est la probabilité d'avoir au moins 4 bons numéros ?
On additionne les cas 4, 5 et 6 bons numéros : **4 bons :** $\binom{6}{4}\binom{43}{2} = 15 \times 903 = 13\,545$ **5 bons :** $\binom{6}{5}\binom{43}{1} = 6 \times 43 = 258$ **6 bons :** $\binom{6}{6}\binom{43}{0} = 1$ $P = \dfrac{13\,545 + 258 + 1}{13\,983\,816} = \dfrac{13\,804}{13\,983\,816} \approx \boxed{9{,}87 \times 10^{-4}}$ Soit environ 1 chance sur 1\,013.
Exercice 37
Avancé
On considère l'ensemble E={1,2,3,…,10}E = \{1, 2, 3, \ldots, 10\}.
1.
Combien de sous-ensembles de EE contiennent l'élément 1 ?
Si 1 est dans le sous-ensemble, on choisit librement les 9 autres éléments (chacun est pris ou non) : $2^9 = \boxed{512}$
2.
Combien de sous-ensembles de EE contiennent 1 et 2 mais pas 3 ?
Les éléments 1 et 2 sont imposés, 3 est exclu. Les 7 éléments restants (4 à 10) sont libres : $2^7 = \boxed{128}$
3.
Combien de sous-ensembles à 4 éléments contiennent au moins un nombre pair ?
Les nombres pairs de $E$ sont $\{2, 4, 6, 8, 10\}$ (5 éléments) et les impairs sont $\{1, 3, 5, 7, 9\}$ (5 éléments). Par le complémentaire : sous-ensembles à 4 éléments **sans aucun pair** (4 impairs parmi 5) : $\binom{5}{4} = 5$ Sous-ensembles à 4 éléments avec au moins un pair : $\binom{10}{4} - 5 = 210 - 5 = \boxed{205}$
4.
Combien de sous-ensembles à 5 éléments de EE ont une somme paire ?
La somme est paire si et seulement si le nombre d'éléments impairs est pair (0, 2 ou 4). Les éléments impairs de $E$ : $\{1,3,5,7,9\}$ (5 éléments). Les pairs : $\{2,4,6,8,10\}$ (5 éléments). **0 impairs, 5 pairs :** $\binom{5}{0}\binom{5}{5} = 1$ **2 impairs, 3 pairs :** $\binom{5}{2}\binom{5}{3} = 10 \times 10 = 100$ **4 impairs, 1 pair :** $\binom{5}{4}\binom{5}{1} = 5 \times 5 = 25$ Total : $1 + 100 + 25 = \boxed{126}$ **Remarque :** $126 = \dfrac{252}{2} = \dfrac{\binom{10}{5}}{2}$. Par symétrie, la moitié des sous-ensembles à 5 éléments ont une somme paire.
Exercice 38
Avancé
On utilise le binôme de Newton pour étudier (1+x)n(1−x)n(1+x)^n(1-x)^n.
1.
Simplifier (1+x)n(1−x)n(1+x)^n(1-x)^n.
$(1+x)^n(1-x)^n = [(1+x)(1-x)]^n = (1-x^2)^n$
2.
Développer (1+x)n(1−x)n(1+x)^n(1-x)^n en identifiant le coefficient de x2px^{2p} dans (1−x2)n(1-x^2)^n.
En posant $y = x^2$ dans $(1-y)^n$ : $(1-x^2)^n = \sum_{p=0}^{n} \binom{n}{p}(-1)^p x^{2p}$ Le coefficient de $x^{2p}$ est $(-1)^p \binom{n}{p}$, et les termes de degré impair sont nuls.
3.
En identifiant le coefficient de x2px^{2p} dans le produit (1+x)n(1−x)n(1+x)^n(1-x)^n développé via le binôme, montrer que ∑k=02p(−1)k(nk)(n2p−k)=(−1)p(np)\displaystyle\sum_{k=0}^{2p} (-1)^k \binom{n}{k}\binom{n}{2p-k} = (-1)^p \binom{n}{p}.
Le coefficient de $x^{2p}$ dans $(1+x)^n$ est $\binom{n}{j}$ pour $x^j$, et dans $(1-x)^n$ est $(-1)^k\binom{n}{k}$ pour $x^k$. Le coefficient de $x^{2p}$ dans le produit est : $\sum_{k=0}^{2p} \binom{n}{k}(-1)^k \binom{n}{2p-k}$ En identifiant avec le résultat de la question 2 : $\boxed{\sum_{k=0}^{2p} (-1)^k \binom{n}{k}\binom{n}{2p-k} = (-1)^p \binom{n}{p}}$
4.
Application : en posant p=0p = 0, retrouver un résultat connu.
Pour $p = 0$ : le coefficient de $x^0$ est : $\sum_{k=0}^{0} (-1)^0 \binom{n}{0}\binom{n}{0} = 1$ Et $(-1)^0 \binom{n}{0} = 1$. ✓ Pour $p = 1$ (plus intéressant) : $\binom{n}{0}\binom{n}{2} - \binom{n}{1}^2 + \binom{n}{2}\binom{n}{0} = -\binom{n}{1}$ $2\binom{n}{2} - n^2 = -n \implies n(n-1) - n^2 = -n \implies -n = -n \quad ✓$
Exercice 39
Avancé
Un sac contient 10 jetons numérotés de 1 à 10. On tire successivement et sans remise 4 jetons.
1.
Combien de tirages ordonnés de 4 jetons peut-on effectuer ?
C'est un arrangement de 4 parmi 10 : $A_{10}^4 = 10 \times 9 \times 8 \times 7 = \boxed{5\,040}$
2.
Combien de tirages ordonnés donnent les jetons dans l'ordre croissant ?
Un tirage ordonné croissant correspond à un **unique** sous-ensemble de 4 jetons (l'ordre est imposé). Il y a autant de tirages ordonnés croissants que de combinaisons de 4 parmi 10 : $\binom{10}{4} = 210$ **Autrement dit :** sur les $4! = 24$ ordres possibles d'un même sous-ensemble, un seul est croissant. $\dfrac{5\,040}{24} = \boxed{210}$
3.
Combien de tirages non ordonnés contiennent exactement 2 nombres pairs et 2 impairs ?
Nombres pairs dans $\{1, \ldots, 10\}$ : $\{2, 4, 6, 8, 10\}$, soit 5. Nombres impairs : $\{1, 3, 5, 7, 9\}$, soit 5. $\binom{5}{2} \times \binom{5}{2} = 10 \times 10 = \boxed{100}$
4.
Combien de tirages non ordonnés contiennent des jetons dont la somme est paire ?
La somme de 4 nombres est paire si et seulement si le nombre d'impairs est pair (0, 2 ou 4). **0 impairs :** $\binom{5}{0}\binom{5}{4} = 1 \times 5 = 5$ **2 impairs :** $\binom{5}{2}\binom{5}{2} = 10 \times 10 = 100$ **4 impairs :** $\binom{5}{4}\binom{5}{0} = 5 \times 1 = 5$ $5 + 100 + 5 = \boxed{110}$ **Vérification :** Total = $\binom{10}{4} = 210$. Somme impaire : $210 - 110 = 100$. Les cas « somme paire » et « somme impaire » ne sont pas symétriques car les 4 éléments sont tirés sans remise.
Exercice 40
Avancé
On place au hasard nn points sur un cercle (n≥2n \geq 2). On trace toutes les cordes possibles.
1.
Combien de cordes peut-on tracer ?
Chaque corde relie 2 points distincts. Le nombre de cordes est : $\binom{n}{2} = \dfrac{n(n-1)}{2}$
2.
Application numérique pour n=6n = 6 et n=10n = 10.
Pour $n = 6$ : $\binom{6}{2} = \dfrac{6 \times 5}{2} = \boxed{15}$ cordes. Pour $n = 10$ : $\binom{10}{2} = \dfrac{10 \times 9}{2} = \boxed{45}$ cordes.
3.
Combien de points d'intersection y a-t-il à l'intérieur du cercle si aucune intersection n'est triple (aucun point intérieur n'appartient à plus de 2 cordes) ?
Deux cordes se coupent à l'intérieur du cercle si et seulement si leurs 4 extrémités sont distinctes. En effet, 4 points sur un cercle déterminent exactement un point d'intersection intérieur (celui des 2 « diagonales » du quadrilatère convexe). Le nombre de points d'intersection intérieurs est donc le nombre de façons de choisir 4 points parmi $n$ : $\binom{n}{4}$
4.
Application numérique pour n=6n = 6.
$\binom{6}{4} = \binom{6}{2} = \boxed{15}$ Avec 6 points sur un cercle et la condition de position générale, on obtient 15 cordes et 15 points d'intersection intérieurs.
4 problèmes de synthèse
Problème 1 — Codes d'accès et sécurité
Facile
Une entreprise utilise des codes d'accès composés de 4 caractères. Chaque caractère est soit une lettre majuscule (26 lettres), soit un chiffre (0 à 9).

Partie A — Codes sans contrainte

1.
Combien de codes d'accès peut-on former si les répétitions sont autorisées ?
Chaque position offre $26 + 10 = 36$ choix. C'est une 4-liste avec répétition de 36 caractères : $36^4 = 1\,679\,616$ Il y a $\boxed{1\,679\,616}$ codes possibles.
2.
Combien de codes ont tous leurs caractères distincts ?
C'est un arrangement de 4 parmi 36 : $36 \times 35 \times 34 \times 33 = \boxed{1\,413\,720}$

Partie B — Codes avec contraintes

3.
Combien de codes commencent par une lettre et finissent par un chiffre ?
Position 1 : 26 choix (lettre). Positions 2 et 3 : 36 choix chacune. Position 4 : 10 choix (chiffre). $26 \times 36 \times 36 \times 10 = 26 \times 12\,960 = \boxed{336\,960}$
4.
Combien de codes contiennent au moins un chiffre ?
Par le complémentaire : on retire les codes composés uniquement de lettres. Codes sans aucun chiffre : $26^4 = 456\,976$. Codes avec au moins un chiffre : $36^4 - 26^4 = 1\,679\,616 - 456\,976 = \boxed{1\,222\,640}$
5.
On impose que le code contienne au moins une lettre ET au moins un chiffre. Combien de tels codes existe-t-il ?
Par inclusion-exclusion. On retire les codes sans lettre (que des chiffres) et les codes sans chiffre (que des lettres) : - Codes que des chiffres : $10^4 = 10\,000$ - Codes que des lettres : $26^4 = 456\,976$ Codes avec au moins une lettre et au moins un chiffre : $36^4 - 10^4 - 26^4 = 1\,679\,616 - 10\,000 - 456\,976 = \boxed{1\,212\,640}$
Problème 2 — Formation d'une commission municipale
Intermédiaire
Un conseil municipal est composé de 12 membres : 7 élus du parti A et 5 élus du parti B. On souhaite former une commission de 5 membres.

Partie A — Dénombrement de base

1.
Combien de commissions de 5 membres peut-on former sans contrainte ?
$\binom{12}{5} = \dfrac{12 \times 11 \times 10 \times 9 \times 8}{5!} = \dfrac{95\,040}{120} = \boxed{792}$
2.
Combien de commissions contiennent exactement 3 élus du parti A et 2 du parti B ?
$\binom{7}{3} \times \binom{5}{2} = 35 \times 10 = \boxed{350}$
3.
Combien de commissions contiennent une majorité d'élus du parti A (au moins 3) ?
On additionne les cas 3A+2B, 4A+1B, 5A+0B : $\binom{7}{3}\binom{5}{2} + \binom{7}{4}\binom{5}{1} + \binom{7}{5}\binom{5}{0} = 350 + 35 \times 5 + 21 \times 1 = 350 + 175 + 21 = \boxed{546}$

Partie B — Commission avec président

4.
On désigne un président parmi les 5 membres de la commission. Combien de commissions avec président peut-on former ?
On choisit d'abord la commission ($\binom{12}{5}$), puis le président parmi les 5 membres : $\binom{12}{5} \times 5 = 792 \times 5 = \boxed{3\,960}$ **Alternative :** on choisit d'abord le président (12 choix) puis 4 membres parmi les 11 restants : $12 \times \binom{11}{4} = 12 \times 330 = 3\,960$ ✓.
5.
Combien de commissions avec président sont telles que le président appartient au parti A et que la commission contient exactement 2 élus du parti B ?
Le président est du parti A : 7 choix. La commission contient 2 élus du parti B : $\binom{5}{2} = 10$ choix. Il reste 2 places pour des élus du parti A (parmi les 6 restants) : $\binom{6}{2} = 15$. $7 \times 10 \times 15 = \boxed{1\,050}$
Problème 3 — Explorations autour du binôme de Newton
Difficile
On note (nk)\binom{n}{k} le coefficient binomial « kk parmi nn ». On rappelle la formule du binôme :

(a+b)n=∑k=0n(nk)an−kbk(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

Partie A — Calcul de sommes

1.
En choisissant des valeurs appropriées de aa et bb, montrer que ∑k=0n(nk)=2n\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n.
On pose $a = 1$ et $b = 1$ dans la formule du binôme : $(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k}$ Donc $\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$. $\square$
2.
En posant a=1a = 1 et b=−1b = -1, montrer que la somme alternée des coefficients binomiaux est nulle (pour n≥1n \geq 1).
$(1+(-1))^n = 0^n = 0$ pour $n \geq 1$. Or $(1+b)^n = \sum_{k=0}^{n} \binom{n}{k} b^k$ avec $b = -1$ : $0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^k = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n}$ $\square$
3.
En additionnant les résultats des questions 1 et 2, en déduire que la somme des (nk)\binom{n}{k} pour kk pair vaut 2n−12^{n-1}.
Question 1 : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ $(*)$ Question 2 : $\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ $(**)$ En faisant $(*)+(** )$ : $2\sum_{\substack{k=0 \ k \text{ pair}}}^{n} \binom{n}{k} = 2^n$ Donc $\displaystyle\sum_{k \text{ pair}} \binom{n}{k} = 2^{n-1}$. $\square$

Partie B — Application au calcul approché

4.
Développer (1+x)6(1+x)^6 en utilisant le binôme.
$(1+x)^6 = \sum_{k=0}^{6} \binom{6}{k} x^k = 1 + 6x + 15x^2 + 20x^3 + 15x^4 + 6x^5 + x^6$
5.
En posant x=0,01x = 0{,}01, calculer une valeur approchée de 1,0161{,}01^6.
$1{,}01^6 = (1+0{,}01)^6 = 1 + 6(0{,}01) + 15(0{,}01)^2 + 20(0{,}01)^3 + \cdots$ $= 1 + 0{,}06 + 15 \times 10^{-4} + 20 \times 10^{-6} + \cdots$ $= 1 + 0{,}06 + 0{,}0015 + 0{,}00002 + \cdots \approx \boxed{1{,}06152}$ Les termes suivants sont négligeables ($< 10^{-7}$).
6.
Déterminer le coefficient de x3x^3 dans (2−x)8(2-x)^8.
On écrit $(2-x)^8 = \sum_{k=0}^{8} \binom{8}{k} 2^{8-k}(-x)^k = \sum_{k=0}^{8} \binom{8}{k}(-1)^k 2^{8-k} x^k$. Pour $k = 3$ : $\binom{8}{3}(-1)^3 \cdot 2^5 = 56 \times (-1) \times 32 = \boxed{-1\,792}$
Problème 4 — Chemins sur une grille et coefficients binomiaux
Avancé
On se place dans un quadrillage. Un chemin part de l'origine O=(0,0)O = (0,0) et se dirige vers un point M=(p,q)M = (p,q) (p,q∈Np, q \in \mathbb{N}) en effectuant des pas élémentaires : un pas vers la droite (D) ou un pas vers le haut (H).

Partie A — Formule générale

1.
Montrer que le nombre de chemins de OO à M=(p,q)M = (p,q) est (p+qp)\binom{p+q}{p}.
Un chemin de $O$ à $(p,q)$ est composé de $p$ pas D et $q$ pas H, soit $p+q$ pas au total. Un chemin est entièrement déterminé par le choix des positions des $p$ pas D parmi les $p+q$ pas : $\boxed{\binom{p+q}{p}} = \binom{p+q}{q}$ (On aurait aussi pu choisir les positions des $q$ pas H.)
2.
Vérifier cette formule pour (p,q)=(3,2)(p,q) = (3,2).
Nombre de chemins : $\binom{5}{3} = \dfrac{5 \times 4 \times 3}{3!} = 10$. On peut les lister : DDDVV, DDVDV, DDVVD, DVDDV, DVDVD, DVVDD, VDDDV, VDDVD, VDVDD, VVDDD. Bien 10 chemins ✓.

Partie B — Passage par un point intermédiaire

3.
Montrer que le nombre de chemins de OO à (p,q)(p,q) passant par un point intermédiaire I=(a,b)I = (a,b) (avec 0≤a≤p0 \leq a \leq p et 0≤b≤q0 \leq b \leq q) est (a+ba)×((p−a)+(q−b)p−a)\binom{a+b}{a} \times \binom{(p-a)+(q-b)}{p-a}.
Un chemin passant par $I = (a,b)$ se décompose en : - Un chemin de $O$ à $I$ : $\binom{a+b}{a}$ chemins - Un chemin de $I$ à $M$ : $\binom{(p-a)+(q-b)}{p-a}$ chemins Par le principe multiplicatif, le nombre total est : $\boxed{\binom{a+b}{a} \times \binom{(p-a)+(q-b)}{p-a}}$
4.
Application : combien de chemins de (0,0)(0,0) à (5,4)(5,4) passent par (2,1)(2,1) puis par (4,3)(4,3) ?
Le chemin se décompose en 3 étapes : $(0,0) \to (2,1)$ : $\binom{3}{2} = 3$ $(2,1) \to (4,3)$ : $\binom{4}{2} = 6$ $(4,3) \to (5,4)$ : $\binom{2}{1} = 2$ Total : $3 \times 6 \times 2 = \boxed{36}$

Partie C — Retrouver la formule de Pascal

5.
En considérant les chemins de OO à (p,q)(p,q), montrer que (p+qp)=(p+q−1p−1)+(p+q−1p)\binom{p+q}{p} = \binom{p+q-1}{p-1} + \binom{p+q-1}{p}.
Tout chemin arrivant en $(p,q)$ effectue un **dernier pas** qui est soit D soit H : - Si le dernier pas est **D** : le chemin passe par $(p-1,q)$ avant. Nombre de chemins de $O$ à $(p-1,q)$ : $\binom{p-1+q}{p-1}$. - Si le dernier pas est **H** : le chemin passe par $(p,q-1)$ avant. Nombre de chemins de $O$ à $(p,q-1)$ : $\binom{p+q-1}{p}$. Ces deux cas sont **disjoints** et couvrent tous les chemins. Donc : $\binom{p+q}{p} = \binom{p+q-1}{p-1} + \binom{p+q-1}{p}$ En posant $n = p+q$ et $k = p$, on retrouve la **formule de Pascal** : $\boxed{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}$
6.
En sommant les chemins de OO à (n,0)(n,0), (n−1,1)(n-1,1), (n−2,2)(n-2,2), …\ldots, (0,n)(0,n) passant par la diagonale, retrouver que ∑k=0n(nk)=2n\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n.
Les points $(n-k, k)$ pour $k = 0, 1, \ldots, n$ sont tous les points de la « anti-diagonale » $x + y = n$. Le nombre de chemins de $O$ à $(n-k,k)$ est $\binom{n}{k}$. Or un chemin de longueur $n$ (partant de $O$) arrive **nécessairement** en un de ces points, et les destinations sont disjointes. Le nombre total de chemins de longueur $n$ est $2^n$ (chaque pas est D ou H, indépendamment). Donc : $\sum_{k=0}^{n} \binom{n}{k} = 2^n \quad \square$ C'est une démonstration **combinatoire** de cette identité (sans utiliser le binôme de Newton).