Tale spé · Chapitre 01 · Algèbre et géométrie

Devoir surveillé — Combinatoire et dénombrement

Sujet type, 120 min, barème sur 20 points. À faire en conditions réelles avant de regarder le corrigé.

Sujet type DS — 120 min, barème sur 20 points. Faites-le en conditions réelles avant de regarder le corrigé (PDF).

Exercice 1 (4 points) — Automatismes

Les calculs de cet exercice doivent être menés sans calculatrice ; on détaillera les étapes.

(1 point) Calculer chacun des nombres suivants :

a. $5!$
b. $\frac{8!}{6!}$
c. $\frac{100!}{98!}$
d. $\frac{7!}{3! \times 4!}$
(1 point) Calculer chacun des coefficients binomiaux suivants à l'aide de la formule $(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k!}$ , en utilisant si besoin la propriété de symétrie :

a. $(\binom{6}{2})$
b. $(\binom{9}{3})$
c. $(\binom{8}{4})$
d. $(\binom{20}{18})$
(1 point) Compléter chaque égalité à l'aide de la relation de Pascal :

a. $(\binom{7}{2}) + (\binom{7}{3}) = (\binom{\dots}{\dots})$
b. $(\binom{11}{5}) + (\binom{11}{\dots}) = (\binom{12}{6})$
(1 point) Déterminer l'entier $n ⩾ 2$ tel que $(\binom{n}{2}) = 28$ .

Exercice 2 (5 points) — Choisir le bon modèle

Pour chacune des cinq situations suivantes, indiquer si l'on compte des $k$ -uplets (résultat $n^{k}$ ), des $k$ -uplets d'éléments distincts (résultat $n (n - 1) \dots (n - k + 1)$ ) ou des combinaisons (résultat $(\binom{n}{k})$ ). Justifier le choix en une phrase, en répondant aux deux questions : l'ordre compte-t-il ? les répétitions sont-elles possibles ? Effectuer ensuite le calcul.

(1 point) À la médiathèque, un abonné emprunte $3$ romans parmi les $25$ nouveautés du rayon littérature.
(1 point) Le digicode d'un immeuble est un code de $4$ caractères, chacun choisi parmi les chiffres de $0$ à $9$ et les lettres $A$ et $B$ .
(1 point) Au tiercé, on parie sur les $3$ premiers chevaux, dans l'ordre d'arrivée, d'une course de $12$ chevaux (sans ex æquo).
(1 point) Une association comptant $18$ membres élit une commission de $5$ personnes, sans rôle particulier.
(1 point) Un QCM comporte $6$ questions ; pour chacune, on coche exactement une réponse parmi les $4$ proposées. On compte les grilles de réponses complètes possibles.

Exercice 3 (4 points) — Coefficients binomiaux : démonstration et applications

(1 point) Recopier le tableau ci-dessous et compléter les lignes $4$ à $6$ du triangle de Pascal :

$n \ k$ $0$ $1$ $2$ $3$ $4$ $5$ $6$

$0$ $1$

$1$ $1$ $1$

$2$ $1$ $2$ $1$

$3$ $1$ $3$ $3$ $1$

$4$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$

$5$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$

$6$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$ $\dots$
Démonstration du cours. Soit $n$ et $k$ deux entiers tels que $1 ⩽ k ⩽ n$ . Soit $E$ un ensemble à $n + 1$ éléments et $a$ un élément fixé de $E$ . On classe les parties de $E$ à $k$ éléments en deux catégories : celles qui contiennent $a$ et celles qui ne contiennent pas $a$ .

a. (1 point) Montrer que le nombre de parties de $E$ à $k$ éléments qui contiennent $a$ est $(\binom{n}{k - 1})$ , et que le nombre de celles qui ne contiennent pas $a$ est $(\binom{n}{k})$ .

b. (1 point) En déduire, à l'aide du principe additif, la relation de Pascal :
$(\binom{n}{k - 1}) + (\binom{n}{k}) = (\binom{n + 1}{k}) .$
(1 point) Application : calculer $\sum_{k = 0}^{8} (\binom{8}{k})$ en citant précisément le résultat du cours utilisé.

$n \ k$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$5$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$6$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Exercice 4 (4 points) — Chemins dans une grille

Sur la grille ci-dessous, on se déplace uniquement d'un pas vers la droite (noté $D$ ) ou d'un pas vers le haut (noté $H$ ). On part du point $A = (0; 0)$ , en bas à gauche, pour rejoindre le point $B = (4; 3)$ , en haut à droite. Le point $C = (2; 2)$ est marqué sur la grille.

Grille de 4 pas sur 3 : chemins de A à B, point C en (2;2)

(1 point) Justifier que les chemins de $A$ à $B$ correspondent exactement aux mots de $7$ lettres écrits avec les lettres $D$ et $H$ et comportant exactement $3$ lettres $H$ .
(1 point) En déduire le nombre total de chemins de $A$ à $B$ .
(1 point) Déterminer le nombre de chemins de $A$ à $B$ qui passent par le point $C$ .
(1 point) En déduire le nombre de chemins de $A$ à $B$ qui ne passent pas par le point $C$ .

Exercice 5 (3 points) — Algorithme : ligne du triangle de Pascal

On souhaite construire la ligne $n$ du triangle de Pascal, c'est-à-dire la liste $[(\binom{n}{0}), (\binom{n}{1}), \dots, (\binom{n}{n})]$ , à l'aide de la relation de Pascal. On propose le script Python à trous suivant :

def ligne_suivante(L):
    """Reçoit la ligne n du triangle de Pascal, renvoie la ligne n + 1."""
    n = len(L)
    M = [1]
    for k in range(n - 1):
        M.append(L[k] + ...)   # trou 1
    M.append(1)
    return M

def ligne(n):
    """Renvoie la ligne n du triangle de Pascal."""
    L = [1]
    for i in range(n):
        L = ...   # trou 2
    return L

(1,5 point) Recopier et compléter les deux instructions incomplètes (trou 1 et trou 2), en justifiant brièvement le trou 1 à l'aide de la relation de Pascal.
(0,5 point) Donner la liste renvoyée par l'appel ligne(4).
(1 point) Que vaut la somme des éléments de la liste renvoyée par l'appel ligne(10) ? Justifier par une propriété du cours (le calcul explicite de la liste n'est pas demandé).

Le sujet du DS(PDF, 56 Ko)Le corrigé du DS(PDF, 83 Ko)

Bloqué sur « Combinatoire et dénombrement » ?

On peut le travailler ensemble dès cette semaine. Une séance ciblée sur ce chapitre, et vous repartez au minimum avec une méthode.

Réserver une séance

$n \ k$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$5$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$6$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

n \ k

0

1

2

3

4

5

6

0

1

1

1

1

2

1

2

1

3

1

3

3

1

4

\dots

\dots

\dots

\dots

\dots

5

\dots

\dots

\dots

\dots

\dots

\dots

6

\dots

\dots

\dots

\dots

\dots

\dots

\dots

def ligne_suivante(L): """Reçoit la ligne n du triangle de Pascal, renvoie la ligne n + 1.""" n = len(L) M = [1] for k in range(n - 1): M.append(L[k] + ...) # trou 1 M.append(1) return M def ligne(n): """Renvoie la ligne n du triangle de Pascal.""" L = [1] for i in range(n): L = ... # trou 2 return L