Exercices : Coefficient binomial
En combinatoire, le coefficient binomial est utilisé pour désigner le nombre de façons possibles de choisir un sous-ensemble d'objets d'une taille k dans un ensemble plus grand de taille n avec \(k \le n\).
Le coefficient binomial est noté \(\binom{n}{k}\) et vaut : $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Le coefficient binomial indique le nombre de combinaisons possibles de k objets à partir de n.
- \(\binom{n}{0} = \binom{n}{n} = 1\)
- \(\binom{n}{k} = \binom{n}{n-k}\) (symétrie)
- \(\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}\) (formule de Pascal)
n = 5, k = 2
10
Le nombre de façons de choisir 2 objets parmi 5 est \(\binom{5}{2} = \frac{5!}{2!3!} = \frac{120}{2 \times 6} = 10\).
n = 100, k = 5
75287520
n = 70, k = 3
54740
- 1 ≤ n ≤ 1000
- 0 ≤ k ≤ n
Calcul du coefficient binomial
Écrire un programme qui prend deux valeurs n et k et renvoie la valeur du coefficient binomial \(\binom{n}{k}\).
Solution 1 : Approche récursive (formule de Pascal)
Une importante relation, la formule de Pascal, lie les coefficients binomiaux : $$\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}$$ avec \(\binom{n}{0}=1\) et \(\binom{n}{n}=1\).
Voici une implémentation récursive simple qui suit la structure récursive mentionnée ci-dessus.
#include <iostream>
using namespace std;
int coefBinomial(int n, int k){
if (k > n)
return 0;
if (k == 0 || k == n)
return 1;
return coefBinomial(n-1, k-1) + coefBinomial(n-1, k);
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n, k) << endl;
return 0;
}def coef_binomial(n, k):
"""
Calcule le coefficient binomial C(n,k) de manière récursive
en utilisant la formule de Pascal.
"""
if k > n:
return 0
if k == 0 or k == n:
return 1
return coef_binomial(n-1, k-1) + coef_binomial(n-1, k)
# Test
n, k = map(int, input().split())
print(coef_binomial(n, k))- Complexité temporelle : O(2ⁿ) dans le pire cas (exponentielle)
- Complexité spatiale : O(n) pour la pile d'appels
Il convient de noter que la fonction ci-dessus calcule encore et encore les mêmes sous-problèmes. Pour n = 5 et k = 2, la fonction C(3,1) est appelée deux fois. Pour de grandes valeurs de n, il y aura de nombreux sous-problèmes communs.
Solution 2 : Programmation dynamique (bottom-up)
Les mêmes sous-problèmes sont appelés à nouveau, ce problème a la propriété de chevauchement de sous-problèmes, de sorte que le problème peut être résolu à l'aide de la programmation dynamique.
On construit une table triangulaire où C[i][j] = coefficient binomial C(i,j).
#include <iostream>
#include <algorithm>
using namespace std;
int coefBinomial(int n, int k){
int C[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= min(i, k); j++) {
// cas de base
if (j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n, k) << endl;
return 0;
}def coef_binomial_dp(n, k):
"""
Calcule C(n,k) par programmation dynamique (bottom-up).
"""
# Créer une table (n+1) x (k+1)
C = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(n+1):
for j in range(min(i, k) + 1):
# Cas de base
if j == 0 or j == i:
C[i][j] = 1
else:
C[i][j] = C[i-1][j-1] + C[i-1][j]
return C[n][k]
# Test
n, k = map(int, input().split())
print(coef_binomial_dp(n, k))- Complexité temporelle : O(n × k)
- Complexité spatiale : O(n × k)
Solution 3 : Approche optimisée (O(min(k, n-k)))
Nous pouvons calculer le coefficient binomial en temps linéaire si nous observons que : $$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n \times (n-1) \times (n-2) \times \dots \times (n-k+1)}{k!}$$
Il faut noter que \(\binom{n}{k} = \binom{n}{n-k}\), on peut donc prendre le minimum de k et n-k pour minimiser le nombre d'opérations.
#include <iostream>
using namespace std;
int coefBinomial(int n, int k){
// Utiliser la symétrie pour réduire les calculs
if (k > n - k)
k = n - k;
int coef = 1;
/*
Calculer la valeur de [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1]
*/
for (int i = 0; i < k; i++){
coef *= (n - i);
coef /= (i + 1);
}
return coef;
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n, k) << endl;
return 0;
}def coef_binomial_opt(n, k):
"""
Calcule C(n,k) de manière optimisée en O(min(k, n-k)).
"""
# Utiliser la symétrie pour réduire les calculs
if k > n - k:
k = n - k
coef = 1
# Calculer n*(n-1)*...*(n-k+1) / k!
for i in range(k):
coef = coef * (n - i)
coef = coef // (i + 1)
return coef
def coef_binomial_float(n, k):
"""
Version utilisant des flottants (attention aux arrondis pour grands n).
"""
from math import comb # Python 3.8+
return comb(n, k)
# Tests
n, k = map(int, input().split())
print(f"C({n},{k}) = {coef_binomial_opt(n, k)}")- Complexité temporelle : O(min(k, n-k))
- Complexité spatiale : O(1)
Entrée: 5 2 → Sortie: 10 Entrée: 100 5 → Sortie: 75287520 Entrée: 70 3 → Sortie: 54740
Comparaison des solutions
| Solution | Complexité temporelle | Complexité spatiale | Avantages / Inconvénients |
|---|---|---|---|
| Récursive (Pascal) | O(2ⁿ) exponentielle | O(n) (pile) | Simple mais très inefficace pour n > 20 |
| Programmation dynamique | O(n × k) | O(n × k) | Efficace pour n modéré, mais mémoire importante |
| Optimisée (linéaire) | O(min(k, n-k)) | O(1) | Meilleure solution, idéale pour tous les cas |
Pour calculer des coefficients binomiaux, la solution 3 (optimisée) est la meilleure : elle est rapide (linéaire), utilise peu de mémoire et gère de grandes valeurs.
En Python 3.8+, on peut aussi utiliser la fonction intégrée math.comb(n, k) qui est très optimisée.
- Le coefficient binomial \(\binom{n}{k}\) compte le nombre de combinaisons de k éléments parmi n.
- La formule de Pascal \(\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}\) permet une définition récursive.
- La programmation dynamique évite les recalculs en stockant les résultats intermédiaires.
- La solution optimisée utilise la formule multiplicative et profite de la symétrie \(\binom{n}{k} = \binom{n}{n-k}\).
- Pour de grands nombres, la solution optimisée est la seule utilisable en pratique.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.