Discrete Mathematics — Binomial Identities

Exercises & Solutions — 4 Python labs + 4 math problems

By Pr. El Hadiq Zouhair

Contents

Part A — Python labs

  1. Pascal's-triangle generator easy lab
  2. Row-sum identity verifier easy lab
  3. Vandermonde identity checker medium lab
  4. Catalan numbers via both formulas medium lab

Part B — Mathematical problems

  1. Apply the binomial theorem to $(2+x)^{12}$ easy math
  2. Pascal's identity — stock-portfolio decomposition medium math
  3. Vandermonde & bouquet counting medium math
  4. Hockey-stick & sum of squares hard math

1Pascal's-triangle generator easy lab

Écrire une fonction pascal(n) qui renvoie la liste des $n + 1$ premières lignes du triangle de Pascal (la ligne $i$ contient $\binom{i}{0}, \binom{i}{1}, \ldots, \binom{i}{i}$), sans utiliser math.comb. Chaque nouvelle ligne se construit à partir de la précédente via l'identité de Pascal.

Solution
Python def pascal(n): """Lignes 0 à n du triangle de Pascal via l'identité de Pascal.""" triangle = [[1]] for i in range(1, n + 1): precedente = triangle[-1] nouvelle = [1] for j in range(1, i): nouvelle.append(precedente[j - 1] + precedente[j]) nouvelle.append(1) triangle.append(nouvelle) return triangle T = pascal(5) for ligne in T: print(ligne) # Vérification : ligne 5 == [1, 5, 10, 10, 5, 1] assert T[5] == [1, 5, 10, 10, 5, 1] # Vérification : somme de la ligne n vaut 2**n for n, ligne in enumerate(T): assert sum(ligne) == 2**n print("Toutes les sommes valent 2^n. ✓")
Output [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] Toutes les sommes valent 2^n. ✓

Justification. Chaque entrée intérieure $\binom{i}{j}$ est obtenue par l'identité de Pascal $\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}$. Les extrémités $\binom{i}{0} = \binom{i}{i} = 1$ sont placées directement.

2Row-sum identity verifier easy lab

Écrire un script qui vérifie pour $n = 0, 1, \ldots, 20$ les trois identités :

  1. $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$
  2. $\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$  (pour $n \geq 1$)
  3. $\displaystyle \sum_{k=0}^{n} 2^k \binom{n}{k} = 3^n$

Renvoyer True si elles sont toutes vraies, sinon afficher la première qui échoue.

Solution
Python from math import comb def verifier(n_max=20): for n in range(n_max + 1): s1 = sum(comb(n, k) for k in range(n + 1)) s2 = sum((-1)**k * comb(n, k) for k in range(n + 1)) s3 = sum(2**k * comb(n, k) for k in range(n + 1)) if s1 != 2**n: return f"Échec identité 1 à n={n} : {s1} != {2**n}" if n >= 1 and s2 != 0: return f"Échec identité 2 à n={n} : {s2} != 0" if s3 != 3**n: return f"Échec identité 3 à n={n} : {s3} != {3**n}" return True print(verifier()) # True
Output True

Justification. Les trois identités sont des spécialisations du théorème du binôme $(x+y)^n = \sum \binom{n}{k} x^k y^{n-k}$ avec $(x,y) = (1,1)$, $(-1,1)$ et $(2,1)$ respectivement.

3Vandermonde identity checker medium lab

Écrire vandermonde(m, n, r) qui vérifie l'identité $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$ pour les paramètres donnés et renvoie le couple (membre_gauche, membre_droit).

Solution
Python from math import comb def vandermonde(m, n, r): gauche = comb(m + n, r) droite = sum(comb(m, k) * comb(n, r - k) for k in range(r + 1)) return gauche, droite for triple in [(8, 12, 5), (15, 15, 10), (20, 20, 20)]: g, d = vandermonde(*triple) print(triple, '→', g, '=', d, ':', g == d) # Corollaire : sum C(n,k)^2 = C(2n, n) for n in (5, 10, 15): s = sum(comb(n, k)**2 for k in range(n + 1)) print(f"n={n}: sum C(n,k)^2 = {s}, C(2n,n) = {comb(2*n, n)}, égalité: {s == comb(2*n, n)}")
Output (8, 12, 5) → 15504 = 15504 : True (15, 15, 10) → 30045015 = 30045015 : True (20, 20, 20) → 137846528820 = 137846528820 : True n=5: sum C(n,k)^2 = 252, C(2n,n) = 252, égalité: True n=10: sum C(n,k)^2 = 184756, C(2n,n) = 184756, égalité: True n=15: sum C(n,k)^2 = 155117520, C(2n,n) = 155117520, égalité: True

Justification. L'identité de Vandermonde se démontre combinatoirement en classant les $r$-sous-ensembles de $\{1, \ldots, m+n\}$ par leur intersection avec $\{1, \ldots, m\}$. Le corollaire $\sum \binom{n}{k}^2 = \binom{2n}{n}$ s'obtient en prenant $m = n, r = n$ et en utilisant la symétrie $\binom{n}{n - k} = \binom{n}{k}$.

4Catalan numbers — deux formules medium lab

Le $n$-ème nombre de Catalan est défini par $C_n = \dfrac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$.

  1. Écrire deux fonctions catalan1(n) et catalan2(n) implémentant chacune une des formules.
  2. Vérifier qu'elles coïncident pour $n = 0, 1, \ldots, 10$.
  3. Vérifier la récurrence $C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$ pour $n \leq 8$.
Solution
Python from math import comb def catalan1(n): """Formule directe : C(2n, n) / (n + 1).""" return comb(2 * n, n) // (n + 1) def catalan2(n): """Formule différence : C(2n, n) - C(2n, n+1).""" return comb(2 * n, n) - comb(2 * n, n + 1) # Comparaison for n in range(11): a, b = catalan1(n), catalan2(n) print(f"C_{n} = {a} = {b}, égalité: {a == b}") # Récurrence convolutive C_{n+1} = sum C_k C_{n-k} for n in range(9): recur = sum(catalan1(k) * catalan1(n - k) for k in range(n + 1)) assert recur == catalan1(n + 1) print("Récurrence convolutive vérifiée. ✓")
Output C_0 = 1 = 1, égalité: True C_1 = 1 = 1, égalité: True C_2 = 2 = 2, égalité: True C_3 = 5 = 5, égalité: True C_4 = 14 = 14, égalité: True C_5 = 42 = 42, égalité: True C_6 = 132 = 132, égalité: True C_7 = 429 = 429, égalité: True C_8 = 1430 = 1430, égalité: True C_9 = 4862 = 4862, égalité: True C_10 = 16796 = 16796, égalité: True Récurrence convolutive vérifiée. ✓

Justification. L'égalité algébrique des deux formules est démontrée slide 19 du cours. La récurrence convolutive $C_{n+1} = \sum C_k C_{n-k}$ s'interprète comme le décompte des arbres binaires enracinés à $n + 1$ feuilles, paramétré par la taille du sous-arbre gauche.

5Binomial theorem appliqué easy math

Considérer le développement de $(2 + x)^{12}$.

  1. Donner le coefficient de $x^5$.
  2. Donner le coefficient de $x^7$.
  3. Quelle est la somme de tous les coefficients ? (Indication : évaluer en $x = 1$.)
  4. Quelle est la somme alternée des coefficients ? (Évaluer en $x = -1$.)
Solution

Le théorème du binôme donne $(2 + x)^{12} = \sum_{k=0}^{12} \binom{12}{k} 2^{12-k} x^k$.

1. Coefficient de $x^5$ : $\binom{12}{5} \cdot 2^7 = 792 \cdot 128 = 101\,376$.

2. Coefficient de $x^7$ : $\binom{12}{7} \cdot 2^5 = 792 \cdot 32 = 25\,344$. (Symétrie $\binom{12}{7} = \binom{12}{5}$.)

3. Somme des coefficients : $(2 + 1)^{12} = 3^{12} = 531\,441$.

4. Somme alternée : $(2 - 1)^{12} = 1^{12} = 1$.

Python — vérification from math import comb print(comb(12, 5) * 2**7) # 101376 print(comb(12, 7) * 2**5) # 25344 print(sum(comb(12, k) * 2**(12-k) for k in range(13))) # 531441 = 3**12 print(sum(comb(12, k) * 2**(12-k) * (-1)**k for k in range(13))) # 1

6Pascal & portefeuille medium math

Maeve doit choisir $8$ actions parmi $20$ pour constituer son portefeuille.

  1. Combien de portefeuilles possibles ?
  2. Maeve a une action favorite. Combien de portefeuilles contiennent cette action ? Combien la excluent ?
  3. Vérifier numériquement l'identité de Pascal $\binom{20}{8} = \binom{19}{7} + \binom{19}{8}$.
  4. Démontrer combinatoirement Pascal en s'appuyant sur cette situation.
Solution

1. $\binom{20}{8} = 125\,970$.

2. Portefeuilles contenant l'action favorite : on la met, puis on choisit les $7$ autres parmi les $19$ restantes. $\binom{19}{7} = 50\,388$.
Portefeuilles l'excluant : $\binom{19}{8} = 75\,582$.

3. $50\,388 + 75\,582 = 125\,970 = \binom{20}{8}$. ✓

4. Démonstration combinatoire de Pascal. Soit $S$ un ensemble à $n$ éléments contenant un élément distingué $a$. Tout sous-ensemble de taille $k$ de $S$ se trouve dans exactement une des deux classes disjointes :

Par la règle de la somme, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. $\square$

Python — vérification from math import comb print(comb(20, 8), comb(19, 7), comb(19, 8)) # 125970 50388 75582 print(comb(19, 7) + comb(19, 8) == comb(20, 8)) # True

7Vandermonde & bouquets medium math

Une fleuriste a $15$ roses et $15$ brins de lavande. Un client veut un bouquet de $10$ fleurs.

  1. Combien de bouquets contiennent exactement $3$ roses et $7$ brins de lavande ?
  2. Combien de bouquets contiennent de $1$ à $3$ roses ?
  3. Combien de bouquets de $10$ fleurs au total ?
  4. Énoncer l'identité de Vandermonde et l'utiliser pour exprimer la question 3 en une seule formule.
Solution

1. $\binom{15}{3} \binom{15}{7} = 455 \cdot 6\,435 = 2\,927\,925$.

2. $\displaystyle \sum_{k=1}^{3} \binom{15}{k}\binom{15}{10-k} = \binom{15}{1}\binom{15}{9} + \binom{15}{2}\binom{15}{8} + \binom{15}{3}\binom{15}{7}$ $= 15 \cdot 5\,005 + 105 \cdot 6\,435 + 455 \cdot 6\,435 = 75\,075 + 675\,675 + 2\,927\,925 = 3\,678\,675$.

3. Par Vandermonde, $\displaystyle \sum_{k=0}^{10} \binom{15}{k}\binom{15}{10-k} = \binom{30}{10} = 30\,045\,015$.

4. Identité de Vandermonde : $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$. Démonstration combinatoire : classer les $r$-sous-ensembles de $\{1, \ldots, m+n\}$ selon le nombre $k$ d'éléments pris dans les $m$ premiers. Dans notre cas $m = n = 15$, $r = 10$, et le total est $\binom{30}{10}$.

Python — vérification from math import comb print(comb(15, 3) * comb(15, 7)) # 2927925 print(sum(comb(15, k) * comb(15, 10 - k) for k in (1, 2, 3))) # 3678675 print(sum(comb(15, k) * comb(15, 10 - k) for k in range(11))) # 30045015 print(comb(30, 10)) # 30045015

8Hockey-stick & sum of squares hard math

Soit $n \geq 1$.

  1. Énoncer l'identité hockey-stick $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$ et la démontrer par double comptage.
  2. Évaluer $\sum_{i=2}^{10} \binom{i}{2}$ et vérifier numériquement.
  3. Démontrer $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$ via Vandermonde.
  4. En déduire la formule asymptotique $\binom{2n}{n} \sim \dfrac{4^n}{\sqrt{\pi n}}$ (Stirling) et en estimer la valeur pour $n = 10$.
Solution

1. Démonstration de l'identité hockey-stick. On compte les $(r+1)$-sous-ensembles de $\{1, 2, \ldots, n+1\}$ classés par leur plus grand élément. Si le maximum est $i + 1$, les $r$ autres éléments se choisissent dans $\{1, \ldots, i\}$ — $\binom{i}{r}$ choix. Le maximum $i + 1$ varie de $r + 1$ à $n + 1$, soit $i \in \{r, r+1, \ldots, n\}$. Par la règle de la somme : $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.$ $\square$

2. $\sum_{i=2}^{10}\binom{i}{2} = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 = 165 = \binom{11}{3}$. ✓

3. Sum of squares via Vandermonde. Avec $m = n, r = n$ : $\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^{n}\binom{n}{k}^2$ par la symétrie $\binom{n}{n-k} = \binom{n}{k}$. $\square$

4. Estimation asymptotique. La formule de Stirling $n! \sim \sqrt{2\pi n}\,(n/e)^n$ donne $\binom{2n}{n} = \dfrac{(2n)!}{(n!)^2} \sim \dfrac{\sqrt{4\pi n}\,(2n/e)^{2n}}{2\pi n \cdot (n/e)^{2n}} = \dfrac{4^n}{\sqrt{\pi n}}.$ Pour $n = 10$ : $4^{10}/\sqrt{10\pi} \approx 1\,048\,576/5.605 \approx 187\,079$ — à comparer à la valeur exacte $\binom{20}{10} = 184\,756$ (erreur $\approx 1.3\%$).

Python — vérification from math import comb, sqrt, pi print(sum(comb(i, 2) for i in range(2, 11)), '==', comb(11, 3)) # 165 == 165 print(sum(comb(10, k)**2 for k in range(11)), '==', comb(20, 10)) # 184756 approx = 4**10 / sqrt(10 * pi) print(f"Approx. Stirling : {approx:.0f}, exact : {comb(20, 10)}") # 187079 vs 184756