Langage de programmation - Mathématiques appliquées

Principes de dénombrement

Les principes de dénombrement regroupent les méthodes mathématiques permettant de déterminer le nombre de possibilités, d'objets, de configurations ou de résultats pouvant être obtenus dans une situation donnée. Ils constituent l'un des fondements de la combinatoire et jouent un rôle majeur dans l'analyse des algorithmes, les probabilités, la génération de données, l'optimisation, les structures discrètes et l'étude de la complexité.

En programmation, de nombreux problèmes reviennent à compter des possibilités sans nécessairement les énumérer toutes. Il peut s'agir de déterminer le nombre de mots de passe possibles, le nombre de chemins dans un graphe, le nombre de permutations d'un tableau, le nombre de sous-ensembles d'une collection ou le nombre de configurations d'un système.

Les principales techniques de dénombrement comprennent le principe additif, le principe multiplicatif, les permutations, les arrangements, les combinaisons, les choix avec répétition, le principe des tiroirs, le principe d'inclusion-exclusion et les méthodes de dénombrement par récurrence.

Dénombrement

Le dénombrement consiste à calculer la cardinalité d'un ensemble fini.

Si un ensemble A contient un nombre fini d'éléments, sa cardinalité est notée :

|A|

Par exemple, si :

A = {a, b, c, d}

alors :

|A| = 4

Dans un problème combinatoire, les éléments de l'ensemble ne sont pas toujours écrits explicitement. Ils peuvent représenter des mots, des chemins, des affectations, des ordres, des sous-ensembles ou des résultats possibles.

Méthode directe

La méthode la plus simple consiste à énumérer toutes les possibilités et à les compter.

Par exemple, les chaînes binaires de longueur 2 sont :

00
01
10
11

Il existe donc :

chaînes binaires de longueur 2.

Cette méthode devient rapidement impraticable lorsque le nombre de possibilités augmente.

Principe additif

Le principe additif est utilisé lorsqu'un choix peut être réalisé selon plusieurs cas mutuellement exclusifs.

Si un premier cas offre :

possibilités et qu'un second cas offre :

possibilités, sans qu'une possibilité appartienne aux deux cas, le nombre total de possibilités est :

m + n

Plus généralement, si les ensembles :

A₁, A₂, ..., A_k

sont deux à deux disjoints, alors :

|A₁ ∪ A₂ ∪ ... ∪ A_k|
=
|A₁| + |A₂| + ... + |A_k|

Exemple du principe additif

Supposons qu'un programme puisse ouvrir :

5 formats d'image ;
3 formats audio.

Si aucun format n'appartient simultanément aux deux catégories, le nombre total de formats pris en charge est :

5 + 3 = 8

Le principe additif correspond donc à une situation où l'on choisit une possibilité dans une catégorie ou dans une autre.

Cas non disjoints

Lorsque les catégories ne sont pas disjointes, l'addition directe compte plusieurs fois les éléments communs.

Pour deux ensembles :

|A ∪ B|
=
|A| + |B| - |A ∩ B|

Par exemple, si :

20 utilisateurs connaissent Java ;
15 utilisateurs connaissent Python ;
8 utilisateurs connaissent les deux langages ;

alors le nombre d'utilisateurs connaissant au moins l'un des deux langages est :

20 + 15 - 8 = 27

Cette formule constitue le premier cas du principe d'inclusion-exclusion.

Principe multiplicatif

Le principe multiplicatif est utilisé lorsqu'un processus est constitué de plusieurs étapes successives.

Si une première étape peut être effectuée de :

façons et qu'une deuxième étape peut être effectuée de :

façons pour chacune des possibilités de la première étape, le nombre total de possibilités est :

m × n

Plus généralement, si un processus comporte k étapes possédant respectivement :

n₁, n₂, ..., n_k

possibilités, alors le nombre total de résultats est :

n₁ × n₂ × ... × n_k

Exemple du principe multiplicatif

Supposons qu'un identifiant soit constitué :

d'une lettre majuscule ;
suivie d'un chiffre.

Il existe :

choix pour la lettre et :

choix pour le chiffre.

Le nombre total d'identifiants est donc :

26 × 10 = 260

Choix successifs avec répétition

Lorsqu'un choix peut être répété à chaque position, le nombre total de possibilités est une puissance.

Si une chaîne contient n positions et que chaque position peut recevoir l'un des k symboles disponibles, alors :

kⁿ

chaînes sont possibles.

Par exemple, le nombre de chaînes binaires de longueur 8 est :

2⁸ = 256

Exemple de mot de passe

Supposons qu'un mot de passe comporte 6 caractères et que chaque caractère puisse être :

une lettre majuscule ;
une lettre minuscule ;
un chiffre.

Le nombre de symboles disponibles est :

26 + 26 + 10 = 62

Si les répétitions sont permises, le nombre de mots de passe est :

62⁶

soit :

56 800 235 584

Choix successifs sans répétition

Lorsqu'un élément choisi ne peut plus être réutilisé, le nombre de possibilités diminue à chaque étape.

Pour choisir successivement k éléments distincts parmi n, on obtient :

n(n-1)(n-2)...(n-k+1)

Cette quantité correspond au nombre d'arrangements de k éléments parmi n.

Factorielle

La factorielle d'un entier naturel n est définie par :

n! =
n × (n-1) × (n-2) × ... × 2 × 1

avec :

0! = 1

La factorielle compte notamment le nombre d'ordres possibles de **n** éléments distincts.

Par exemple :

4! = 4 × 3 × 2 × 1 = 24

Permutations

Une permutation est un arrangement de tous les éléments d'un ensemble dans un ordre donné.

Le nombre de permutations de **n** éléments distincts est :

P(n) = n!

Par exemple, les permutations de :

{A, B, C}

sont :

ABC
ACB
BAC
BCA
CAB
CBA

Il existe donc :

3! = 6

permutations.

Permutations avec répétition

Lorsque certains éléments sont identiques, plusieurs permutations deviennent indiscernables.

Si un ensemble de **n** éléments contient :

n₁

éléments identiques d'un premier type,

n²

éléments identiques d'un deuxième type, et ainsi de suite, le nombre de permutations distinctes est :

n! /
(n₁!n₂!...n_k!)

avec :

n₁+n₂+...+n_k = n

Exemple de permutations avec répétition

Considérons le mot :

BANANE

Il contient 6 lettres :

A apparaît 2 fois ;
N apparaît 2 fois ;
B apparaît 1 fois ;
E apparaît 1 fois.

Le nombre d'ordres distincts est :

6! / (2!2!)

soit :

180

Permutations circulaires

Lorsque des éléments sont placés autour d'un cercle, les configurations obtenues par rotation sont généralement considérées comme identiques.

Le nombre de permutations circulaires de n éléments distincts est :

(n-1)!

Par exemple, le nombre de façons de placer 5 personnes autour d'une table ronde est :

4! = 24

Cette formule suppose que seules les rotations sont identifiées. Si les réflexions sont également considérées comme identiques, le calcul doit être ajusté.

Arrangements

Un arrangement de k éléments parmi n est une sélection ordonnée de k éléments distincts.

Le nombre d'arrangements est :

A(n,k) =
n!/(n-k)!

On peut également écrire :

A(n,k) =
n(n-1)...(n-k+1)

L'ordre est important et les répétitions ne sont pas permises.

Exemple d'arrangement

Supposons qu'une course comporte 10 participants et que l'on souhaite compter les podiums possibles.

Il faut choisir :

le premier ;
le deuxième ;
le troisième.

Le nombre de podiums est :

10 × 9 × 8

soit :

720

On peut écrire :

A(10,3) = 720

Arrangements avec répétition

Lorsque les répétitions sont autorisées, le nombre de séquences ordonnées de longueur k formées à partir de n éléments est :

n^k

Par exemple, le nombre de codes à 4 chiffres est :

10⁴ = 10 000

si les chiffres peuvent être répétés et si les codes commençant par zéro sont autorisés.

Combinaisons

Une combinaison est une sélection non ordonnée de **k** éléments distincts parmi n.

Le nombre de combinaisons est :

C(n,k)
=
n! /
(k!(n-k)!)

Cette valeur est également appelée coefficient binomial.

L'ordre n'a pas d'importance.

Exemple de combinaison

Supposons que l'on choisisse 3 membres parmi un groupe de 10 personnes.

Le nombre de groupes possibles est :

C(10,3)
=
10!/(3!7!)

soit :

120

Le groupe constitué de :

Alice, Bob, Charles

est identique au groupe :

Charles, Alice, Bob

Différence entre arrangement et combinaison

Caractéristique	Arrangement	Combinaison
Ordre important	Oui	Non
Répétition	Non dans la forme classique	Non dans la forme classique
Formule	n!/(n-k)!	n!/(k!(n-k)!)
Exemple	Podium	Comité

Un arrangement peut être interprété comme une combinaison suivie d'une permutation des éléments choisis :

A(n,k) =
C(n,k) × k!

Combinaisons avec répétition

Une combinaison avec répétition permet de choisir k éléments parmi n types, en autorisant plusieurs occurrences du même type.

Le nombre de possibilités est :

C(n+k-1,k)

ou de manière équivalente :

C(n+k-1,n-1)

Cette formule est souvent appelée la méthode des étoiles et des barres.

Exemple de combinaison avec répétition

Supposons que l'on choisisse 4 boules de crème glacée parmi 3 parfums :

Vanille
Chocolat
Fraise

Les répétitions sont autorisées et l'ordre des boules n'est pas pris en compte.

Le nombre de choix est :

C(3+4-1,4)
=
C(6,4)
=
15

Méthode des étoiles et des barres

La méthode des étoiles et des barres permet de compter les solutions entières non négatives de :

x₁+x₂+...+x_n = k

Chaque unité est représentée par une étoile et les séparations entre les variables par des barres.

Par exemple :

***|*||

peut représenter :

x₁ = 3
x₂ = 1
x₃ = 0
x₄ = 0

Le nombre de solutions est :

C(k+n-1,n-1)

Solutions entières positives

Pour compter les solutions entières strictement positives de :

x₁+x₂+...+x_n = k

on impose :

x_i ≥ 1

On pose :

y_i = x_i-1

Les variables y_i sont alors non négatives et satisfont :

y₁+y₂+...+y_n = k-n

Le nombre de solutions est :

C(k-1,n-1)

à condition que :

k ≥ n

Sous-ensembles

Un ensemble contenant n éléments possède :

2ⁿ

sous-ensembles.

Chaque élément offre deux possibilités :

être inclus ;
ne pas être inclus.

Par le principe multiplicatif :

2 × 2 × ... × 2
=
2ⁿ

Sous-ensembles de cardinalité fixée

Le nombre de sous-ensembles contenant exactement k éléments parmi n est :

C(n,k)

En additionnant toutes les tailles possibles, on obtient :

∑_k=0ⁿ C(n,k) = 2ⁿ

Cette identité correspond au nombre total de sous-ensembles.

Chaînes et mots

Pour un alphabet contenant m symboles, le nombre de mots de longueur exactement n est :

mⁿ

Le nombre de mots de longueur inférieure ou égale à n est :

1 + m + m² + ... + mⁿ

Lorsque :

m ≠ 1

cette somme vaut :

(mⁿ⁺¹-1)/(m-1)

Le terme 1 correspond au mot vide.

Dénombrement par complément

Il est parfois plus simple de compter toutes les possibilités puis de soustraire celles qui ne respectent pas la condition.

La formule générale est :

Nombre recherché
=
Nombre total
-
Nombre de cas interdits

Cette méthode est appelée dénombrement par complément.

Exemple par complément

Supposons que l'on souhaite compter les chaînes binaires de longueur 8 contenant au moins un chiffre 1.

Le nombre total de chaînes est :

2⁸ = 256

Une seule chaîne ne contient aucun 1 :

00000000

Le nombre recherché est donc :

256 - 1 = 255

Principe d'inclusion-exclusion

Le principe d'inclusion-exclusion permet de compter l'union de plusieurs ensembles en corrigeant les éléments comptés plusieurs fois.

Pour deux ensembles :

|A ∪ B|
=
|A| + |B| - |A ∩ B|

Pour trois ensembles :

|A ∪ B ∪ C|
=
|A| + |B| + |C|
-
|A ∩ B|
-
|A ∩ C|
-
|B ∩ C|
+
|A ∩ B ∩ C|

Formule générale d'inclusion-exclusion

Pour des ensembles :

A₁, A₂, ..., A_n

on obtient :

|A₁ ∪ ... ∪ A_n|
=
∑|A_i|
-
∑|A_i ∩ A_i|
+
∑|A_i ∩ A_i ∩ A_k|
-
...
+
(-1)^{n+1

|A₁ ∩ ... ∩ A_n|}

Les intersections d'un nombre impair d'ensembles sont ajoutées et celles d'un nombre pair sont soustraites.

Exemple d'inclusion-exclusion

Parmi 100 fichiers :

45 contiennent du code Java ;
35 contiennent du code Python ;
20 contiennent les deux.

Le nombre de fichiers contenant au moins l'un des deux langages est :

45 + 35 - 20 = 60

Le nombre de fichiers ne contenant aucun de ces langages est :

100 - 60 = 40

Principe des tiroirs

Le principe des tiroirs, également appelé principe de Dirichlet, affirme que si plus de n objets sont placés dans n tiroirs, alors au moins un tiroir contient au moins deux objets.

Dans sa forme simple :

n+1 objets

placés dans :

n tiroirs

impliquent qu'un tiroir contient au moins :

2 objets

Principe généralisé des tiroirs

Si N objets sont distribués dans k tiroirs, au moins un tiroir contient au moins :

⌈N/k⌉

objets.

La notation :

⌈x⌉

désigne le plus petit entier supérieur ou égal à x.

Exemple du principe des tiroirs

Dans un groupe de 13 personnes, au moins deux personnes sont nées durant le même mois.

Il existe seulement :

mois possibles.

En plaçant 13 personnes dans 12 catégories, au moins une catégorie contient au moins deux personnes.

Ce principe démontre l'existence d'une répétition sans préciser laquelle.

Applications aux fonctions de hachage

Une table de hachage comportant m emplacements reçoit des clés appartenant à un ensemble beaucoup plus grand.

Si plus de m clefs distinctes sont insérées, au moins deux clés doivent produire le même emplacement.

Cette situation est appelée une collision de hachage.

Le principe des tiroirs montre que les collisions sont inévitables lorsqu'il y a davantage de clés que de valeurs de hachage possibles.

Dénombrement par bijection

Une bijection est une correspondance un à un entre deux ensembles.

Si une bijection existe entre A et B, alors :

|A| = |B|

Le dénombrement par bijection consiste à transformer les objets difficiles à compter en objets appartenant à un ensemble plus facile à dénombrer.

Cette méthode est très utilisée dans les démonstrations combinatoires.

Exemple de bijection

Les sous-ensembles d'un ensemble de n éléments peuvent être mis en bijection avec les chaînes binaires de longueur n.

Pour chaque élément :

1 indique qu'il appartient au sous-ensemble ;
0 indique qu'il n'y appartient pas.

Par exemple :

{a,c}

dans :

{a,b,c,d}

correspond à :

1010

Comme il existe :

2ⁿ

chaînes binaires, il existe également :

2ⁿ

sous-ensembles.

Dénombrement par double comptage

Le double comptage consiste à compter le même ensemble de deux manières différentes.

Si les deux méthodes comptent exactement les mêmes objets, leurs résultats sont égaux.

Cette technique permet de démontrer des identités combinatoires.

Exemple de double comptage

Considérons un groupe de n personnes et comptons le nombre de façons de choisir un comité de k personnes puis un président parmi ses membres.

Première méthode :

C(n,k) × k

Deuxième méthode :

choisir d'abord le président parmi n personnes ;
choisir les k-1 autres membres parmi les n-1 personnes restantes.

On obtient :

n × C(n-1,k-1)

Donc :

kC(n,k)
=
nC(n-1,k-1)

Dénombrement par récurrence

Certains objets peuvent être comptés en fonction d'objets plus petits.

On définit alors une relation de récurrence.

Par exemple, le nombre de chaînes binaires de longueur n ne contenant pas deux 1 consécutifs peut être décomposé selon leur dernier symbole.

Si une chaîne se termine par 0, son préfixe peut être toute chaîne valide de longueur n-1.

Si elle se termine par 1, le symbole précédent doit être 0, et le préfixe restant possède une longueur n-2.

On obtient :

a_n =
a_n-1 + a_n-2

Cette récurrence est liée à la suite de Fibonacci.

Dénombrement par fonction génératrice

Une fonction génératrice regroupe une suite de nombres de dénombrement dans une série :

A(x)
=
∑_n=0∞ a_nxⁿ

Le coefficient :

[xⁿ]A(x)

représente le nombre d'objets de taille n.

La multiplication de fonctions génératrices correspond à la combinaison de choix indépendants et produit une convolution des coefficients.

Exemple avec des pièces de monnaie

Pour des pièces de valeurs :

1, 2 et 5

utilisables en quantité illimitée, la fonction génératrice est :

1/
((1-x)(1-x²)(1-x⁵))

Le coefficient de :

xⁿ

indique le nombre de façons de former la somme n sans tenir compte de l'ordre des pièces.

Dénombrement des chemins dans une grille

Considérons une grille dans laquelle un déplacement est autorisé uniquement :

vers la droite ;
vers le bas.

Pour aller du coin supérieur gauche au coin inférieur droit d'une grille nécessitant :

déplacements vers la droite et :

déplacements vers le bas, il faut ordonner :

r+b

déplacements.

Le nombre de chemins est :

C(r+b,r)

ou :

C(r+b,b)

Exemple de chemins

Supposons qu'un déplacement nécessite :

mouvements vers la droite et :

mouvements vers le bas.

Il faut ordonner les symboles :

D D D B B

Le nombre de chemins est :

5!/(3!2!)

soit :

Dénombrement des arbres

Le nombre d'arbres ou de structures récursives est souvent déterminé par des relations de récurrence ou des fonctions génératrices.

Par exemple, le nombre d'arbres binaires ordonnés possédant n noeuds internes est donné par le nombre de Catalan :

C_n =
1/(n+1)
×
C(2n,n)

Les premières valeurs sont :

1, 1, 2, 5, 14, 42, ...

Dénombrement et probabilités

Dans un univers fini où tous les résultats sont équiprobables, la probabilité d'un événement E est :

P(E)
=
|E|/|Ω|

où :

représente l'ensemble de tous les résultats possibles.

Les principes de dénombrement permettent donc de calculer le numérateur et le dénominateur.

Exemple avec des dés

Deux dés à six faces produisent :

6 × 6 = 36

résultats ordonnés possibles.

Les résultats dont la somme vaut 7 sont :

(1,6)
(2,5)
(3,4)
(4,3)
(5,2)
(6,1)

Il existe donc 6 cas favorables.

La probabilité est :

6/36 = 1/6

Dénombrement et complexité algorithmique

Le nombre de possibilités à explorer détermine souvent la complexité d'un algorithme.

Par exemple :

parcourir tous les sous-ensembles produit 2ⁿ cas ;
parcourir toutes les permutations produit n! cas ;
parcourir tous les couples produit n² cas ;
parcourir toutes les combinaisons de taille k produit C(n,k) cas.

Ces quantités permettent d'estimer le coût d'un algorithme exhaustif.

Explosion combinatoire

L'explosion combinatoire désigne la croissance extrêmement rapide du nombre de possibilités lorsque la taille du problème augmente.

Par exemple :

10! = 3 628 800

mais :

20! =
2 432 902 008 176 640 000

De même :

2¹⁰ = 1 024

alors que :

2¹⁰⁰

est un nombre contenant plus de trente chiffres.

Cette croissance rend souvent l'énumération complète impraticable.

Tableau récapitulatif

Situation	Nombre de possibilités
Choisir un cas parmi des catégories disjointes	Somme des possibilités
Effectuer plusieurs étapes indépendantes	Produit des possibilités
Suite de longueur k avec n choix et répétition	n^k
Arrangement de k éléments parmi n	n!/(n-k)!
Permutation de n éléments	n!
Combinaison de k éléments parmi n	n!/(k!(n-k)!)
Combinaison avec répétition	C(n+k-1,k)
Sous-ensembles d'un ensemble de n éléments	2ⁿ
Permutation circulaire de n éléments	(n-1)!
Solutions non négatives de x₁+...+x_n=k	C(k+n-1,n-1)
Solutions positives de x₁+...+x_n=k	C(k-1,n-1)

Algorithme d'énumération des sous-ensembles

Un ensemble de n éléments possède :

2ⁿ

sous-ensembles.

Chaque masque binaire de n bits représente un sous-ensemble.

MODULE ÉnumérerSousEnsembles(A)

   n ← longueur(A)

   POUR masque ← 0 JUSQU'A 2ⁿ-1
      sousEnsemble ← ensemble vide
      POUR i ← 0 JUSQU'A n-1
         SI le bit i de masque vaut 1 ALORS
            Ajouter A[i] à sousEnsemble
         FIN SI
      FIN POUR
      AFFICHER sousEnsemble
   FIN POUR

Complexité de l'énumération des sous-ensembles

Il existe :

2ⁿ

masques.

Pour chaque masque, l'algorithme examine :

positions.

La complexité temporelle est donc :

O(n2ⁿ)

La mémoire supplémentaire peut être limitée à :

O(n)

si un seul sous-ensemble est construit à la fois.

Algorithme de génération des permutations

MODULE Permuter(tableau,début)
   SI début = longueur(tableau) ALORS
      AFFICHER tableau
      RETOURNER
   FIN SI

   POUR i ← début JUSQU'A longueur(tableau)-1
      Échanger tableau[début] et tableau[i]
      Permuter(tableau,début+1)
      Échanger tableau[début] et tableau[i]
   FIN POUR

Cet algorithme utilise le retour arrière pour produire toutes les permutations.

Complexité de génération des permutations

Il existe :

permutations de n éléments.

Si chaque permutation est copiée ou affichée en temps :

O(n)

la complexité totale est :

O(n × n!)

La génération exhaustive devient rapidement coûteuse.

Algorithme de calcul d'une combinaison

Le coefficient binomial peut être calculé sans produire directement les factorielles.

MODULE Combinaison(n,k)

   SI k < 0 OU k > n ALORS
      RETOURNER 0
   FIN SI

   k ← MINIMUM(k,n-k)
   résultat ← 1

   POUR i ← 1 JUSQU'A k
      résultat ← résultat × (n-k+i) DIV i
   FIN POUR

   RETOURNER résultat

Cette méthode réduit la taille des calculs intermédiaires.

Exemple en Java


import java.math.BigInteger;
 
public class DenombrementSample {
 
    public static BigInteger combinaison(
        int n,
        int k
    ) {
        if (n < 0 || k < 0 || k > n) {
            return BigInteger.ZERO;
        }
 
        k = Math.min(k, n - k);
 
        BigInteger resultat =
            BigInteger.ONE;
 
        for (int i = 1; i <= k; i++) {
            resultat = resultat.multiply(
                BigInteger.valueOf(n - k + i)
            );
 
            resultat = resultat.divide(
                BigInteger.valueOf(i)
            );
        }
 
        return resultat;
    }
 
    public static BigInteger arrangements(
        int n,
        int k
    ) {
        if (n < 0 || k < 0 || k > n) {
            return BigInteger.ZERO;
        }
 
        BigInteger resultat =
            BigInteger.ONE;
 
        for (int i = 0; i < k; i++) {
            resultat = resultat.multiply(
                BigInteger.valueOf(n - i)
            );
        }
 
        return resultat;
    }
 
    public static void main(String[] args) {
        System.out.println(
            "C(10,3) = "
            + combinaison(10, 3)
        );
 
        System.out.println(
            "A(10,3) = "
            + arrangements(10, 3)
        );
    }
}

Le programme affiche :

C(10,3) = 120 A(10,3) = 720

Dépassement de capacité

Les quantités combinatoires augmentent rapidement.

Par exemple :

20! =
2 432 902 008 176 640 000

Cette valeur dépasse la capacité d'un entier signé de 64 bits.

Il est donc souvent nécessaire d'utiliser :

des entiers multiprécision ;
l'arithmétique modulaire ;
des logarithmes ;
des approximations ;
des calculs symboliques.

Approximation de la factorielle

La formule de Stirling permet d'approximer :

pour les grandes valeurs de n :

n!
≈
√(2Πn)(n/e)ⁿ

Sous forme logarithmique :

ln(n!)
≈
n ln(n)-n
+
1/2 ln(2Πn)

Cette approximation permet d'estimer la taille d'un espace de recherche sans calculer exactement la factorielle.

Coefficients binomiaux modulo un entier

Dans certains algorithmes, on cherche :

C(n,k) mod m

plutôt que la valeur exacte.

Des techniques spécialisées peuvent être utilisées :

triangle de Pascal modulo m ;
factorielles et inverses modulaires ;
petit théorème de Fermat lorsque le module est premier ;
théorème de Lucas ;
théorème chinois des restes.

Cette approche évite de manipuler des nombres extrêmement grands.

Programmation dynamique

Plusieurs problèmes de dénombrement peuvent être résolus par programmation dynamique.

Par exemple, le nombre de façons de former une somme S avec certaines pièces peut être calculé par :

MODULE CompterSommes(pièces,S)

   façons[0] ← 1

   POUR CHAQUE pièce DANS pièces
      POUR somme ← pièce JUSQU'A S
         façons[somme] ←
            façons[somme]
            +
            façons[somme-pièce]
      FIN POUR
   FIN POUR
   RETOURNER façons[S]

Le tableau contient le nombre de possibilités pour chaque somme intermédiaire.

Dénombrement exact et énumération

Il faut distinguer :

le calcul du nombre de solutions ;
la génération effective de toutes les solutions.

Le nombre de solutions peut parfois être calculé rapidement, même lorsque leur énumération est impossible en pratique.

Par exemple :

C(1000,500)

peut être calculé à l'aide d'entiers multiprécision, mais produire tous les sous-ensembles correspondants serait irréalisable.

Applications

Les principes de dénombrement sont utilisés dans :

l'analyse des algorithmes ;
les probabilités ;
la cryptographie ;
les mots de passe ;
les systèmes de hachage ;
les graphes ;
les chemins ;
les arbres ;
les permutations ;
les tests exhaustifs ;
l'optimisation combinatoire ;
les bases de données ;
les automates ;
la génération procédurale ;
la bio-informatique ;
la théorie des codes ;
l'intelligence artificielle.

Avantages

Les principes de dénombrement présentent plusieurs avantages :

ils permettent de calculer un nombre de possibilités sans les générer ;
ils facilitent l'analyse des espaces de recherche ;
ils servent de base aux probabilités discrètes ;
ils permettent d'identifier une explosion combinatoire ;
ils fournissent des méthodes de preuve ;
ils relient les ensembles, les suites et les fonctions génératrices ;
ils permettent de comparer plusieurs approches algorithmiques ;
ils aident à concevoir des algorithmes de programmation dynamique.

Limites et précautions

Plusieurs précautions doivent être prises :

il faut déterminer si l'ordre est important ;
il faut déterminer si les répétitions sont permises ;
les catégories du principe additif doivent être disjointes ;
les étapes du principe multiplicatif doivent être correctement définies ;
les objets identiques doivent être pris en compte ;
les symétries peuvent réduire le nombre de configurations distinctes ;
les nombres produits peuvent dépasser les types numériques ordinaires ;
compter les solutions ne fournit pas nécessairement une méthode pour les construire ;
une formule fermée n'existe pas pour tous les problèmes ;
l'énumération exhaustive peut être impraticable malgré un calcul rapide de la cardinalité.

Remarque

Les principes de dénombrement permettent de transformer une question portant sur un grand nombre de configurations en un calcul mathématique structuré. Le principe additif correspond à une séparation en cas, tandis que le principe multiplicatif décrit une succession de choix. Les permutations, les arrangements et les combinaisons précisent ensuite si l'ordre et les répétitions doivent être pris en compte.

En programmation, ces méthodes servent à estimer la taille d'un espace de recherche, à prévoir la complexité d'un algorithme, à calculer des probabilités et à concevoir des solutions par programmation dynamique. Elles préparent naturellement à l'étude du principe d'inclusion-exclusion, du principe des tiroirs, des relations de récurrence, des nombres de Catalan et de l'analyse combinatoire des algorithmes.

Dernière mise à jour : Jeudi, le 16 juillet 2026