Matiko Logo

6 ex.

Difficulté :
L'essentiel du cours (3 notions)

Combinaisons et triangle de Pascal

Définition : Une combinaison de $k$ éléments parmi $n$ est une partie à $k$ éléments d'un ensemble à $n$ éléments. On note $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Propriété : - Symétrie : $\binom{n}{k} = \binom{n}{n-k}$ - Relation de Pascal : $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

Exemple : $\binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$. Par symétrie, $\binom{5}{3} = 10$.

Algorithmes de génération combinatoire

Méthode : 1. Initialiser les bords du triangle de Pascal avec des 1. 2. Calculer chaque terme par la relation de Pascal : $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. 3. Générer les $k$-uplets via des boucles imbriquées.

Exemple : La ligne $n=3$ s'obtient à partir de la ligne $n=2$ ($1, 2, 1$) par $1$, $1+2=3$, $2+1=3$, $1$, soit $1, 3, 3, 1$.

Combinaisons avec répétitions

Définition : Une combinaison avec répétitions de $k$ éléments parmi $n$ est un choix non ordonné de $k$ objets parmi $n$ types distincts, avec répétition autorisée.

Formule : $\binom{n + k - 1}{k}$

Exemple : Choisir 4 boules parmi 3 couleurs avec répétitions donne $\binom{3+4-1}{4} = \binom{6}{4} = 15$ possibilités.

★ Standard

Soit $n$ un entier naturel tel que $n \ge 5$.

On considère l'égalité suivante portant sur les coefficients binomiaux :

$$\binom{n}{3} = \binom{n}{5}$$

En utilisant la propriété de symétrie des combinaisons, déterminer la valeur de l'entier $n$.

Saisir la valeur de $n$.
★★ Avancé

On considère la fonction suivante écrite en langage Python :

def calcul_somme(n):
    L = [1]
    for i in range(1, n + 1):
        ligne = [1]
        for j in range(len(L) - 1):
            ligne.append(L[j] + L[j + 1])
        ligne.append(1)
        L = ligne
    
    total = 0
    for k in range(len(L)):
        if k % 2 == 0:
            total += L[k]
    return total

Déterminer la valeur renvoyée par l'appel calcul_somme(6).
★★ Avancé

On considère la fonction Python suivante conçue pour générer toutes les parties à $2$ éléments d'un ensemble de $n$ éléments distincts :

def generer_parties(n):
    L = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            L.append((i, j))
    return L

Lorsqu'on exécute la commande len(generer_parties(n)) pour un entier $n \geqslant 2$, le programme renvoie la valeur $28$.

Déterminer la valeur de l'entier $n$.

Saisir la valeur de n.
★★ Avancé

Soit $n$ un entier naturel supérieur ou égal à $3$. On considère l'équation suivante :

$$\binom{n}{2} + \binom{n}{3} = 120$$

Déterminer la valeur de l'entier $n$.

Saisir la valeur de $n$.
★★★ Challenge

On considère la fonction Python ci-dessous, où $n$ désigne un entier naturel supérieur ou égal à $3$.

def generer_parties(n):
    compteur = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            compteur += 1
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(j + 1, n + 1):
                compteur += 1
    return compteur

Lors d'une exécution, la commande generer_parties(n) renvoie la valeur $455$.

Saisir la valeur de l'entier $n$.
Approfondissement ★★★ Challenge

On considère l'équation $x_1 + x_2 + x_3 + x_4 = S$, où $S$ est un entier naturel.

On cherche le nombre de quadruplets d'entiers $(x_1, x_2, x_3, x_4)$ vérifiant cette équation avec les contraintes suivantes : $x_1 \ge 1$, $x_2 \ge 2$, $x_3 \ge 0$ et $x_4 \ge 0$.

Rappel : Pour tout entier $n \ge 1$ et tout entier $k \ge 0$, le nombre de $n$-uplets d'entiers naturels $(y_1, y_2, \dots, y_n)$ tels que $y_1 + y_2 + \dots + y_n = k$ est égal à $\binom{n+k-1}{k}$.

Déterminer le plus petit entier $S$ pour lequel le nombre de quadruplets solutions sous ces contraintes est supérieur ou égal à $200$.

Saisir la valeur minimale de $S$.