Dénombrement et preuves combinatoires

De combien de façons peut-on répartir sept unités de travail identiques entre trois équipes nommées ? Avant de choisir une formule, il faut préciser ce qui constitue une répartition. Si seul le nombre d’unités par équipe compte, un résultat est un triplet $(x_1,x_2,x_3)$. Si les sept tâches sont distinctes et que l’on enregistre l’équipe chargée de chacune, on compte d’autres objets.

La carte des mathématiques discrètes donne les formules de base des permutations et des combinaisons. Les preuves combinatoires expliquent pourquoi des nombres sont égaux, comment corriger les recouvrements et pourquoi certaines répartitions sont impossibles.

Définir les objets et leur égalité

Dénombrer consiste à trouver la taille $|S|$ d’un ensemble fini $S$. Il faut préciser ses objets, leurs contraintes et les conditions dans lesquelles deux descriptions représentent le même résultat.

• Une suite conserve les positions : AB et BA sont différentes. Un ensemble conserve les éléments présents ; les deux descriptions représentent $\{A,B\}$.
• Autoriser le choix répété d’une valeur et considérer ses exemplaires comme indiscernables sont deux conditions distinctes.
• Plusieurs chemins de construction peuvent aboutir au même résultat. Avant de compter les chemins, vérifier que ce sont bien les objets demandés.

Par exemple, les suites de longueur deux sur A et B, avec répétition, sont AA, AB, BA et BB. Si l’on ne conserve que le nombre de chaque lettre, AB et BA se confondent et il reste trois résultats. On ne peut pas diviser le nombre de suites par un facteur uniforme : AA n’a qu’un ordre possible, contre deux pour AB. Les notes de dénombrement de Berkeley CS70 exigent que chaque résultat ait le même nombre d’antécédents pour appliquer la règle de division.

Multiplier les étapes, additionner les cas disjoints

Si chaque objet se construit d’une seule façon en $k$ étapes et que chaque préfixe valide offre exactement $n_i$ choix à l’étape $i$, la règle du produit généralisée (MIT, section 14.3) donne $\prod_{i=1}^k n_i$. Les choix disponibles peuvent dépendre des étapes précédentes ; leur nombre doit rester constant à un même niveau. Choisir une lettre parmi trois lettres distinctes, puis un chiffre parmi quatre chiffres distincts, donne $3\times4=12$ suites dans l’ordre lettre–chiffre.

Lorsque les branches n’ont pas la même taille, on les compte séparément, puis on additionne. Si un premier choix A autorise deux caractères suivants et un premier choix B en autorise trois, le total vaut $2+3=5$.

La règle de la somme s’applique aux cas deux à deux disjoints. Pour des ensembles finis $S_1,\ldots,S_k$ deux à deux disjoints,

$$\left|\bigcup_{i=1}^k S_i\right|=\sum_{i=1}^k|S_i|.$$

Cette condition figure dans Mathematics for Computer Science du MIT, section 14.2. Les chaînes décimales de longueur deux ou trois, avec des zéros initiaux autorisés, forment deux classes disjointes selon leur longueur : on en compte $10^2+10^3=1100$. Les classes « contient A » et « contient B » se recouvrent sur les chaînes contenant les deux lettres ; il faut alors corriger le comptage.

Prouver des identités par bijection et double dénombrement

Une bijection associe les éléments de deux ensembles : chaque élément de départ a une image et chaque élément d’arrivée a exactement un antécédent. Donner l’application et son inverse prouve que les deux ensembles ont la même taille.

Dans un ensemble fixé de $n$ éléments, associons à chaque sous-ensemble de $k$ éléments son complément, qui contient $(n-k)$ éléments. Prendre à nouveau le complément redonne le sous-ensemble de départ. Pour $0\le k\le n$,

$$\binom nk=\binom n{n-k}.$$

Choisir deux personnes parmi cinq revient ainsi à choisir les trois personnes laissées de côté. Chaque dénombrement donne 10.

Le double dénombrement compte le même ensemble de deux manières. Pour $n\ge1$ et $1\le k\le n$, un résultat est un comité de $k$ personnes dont un membre est désigné responsable. Choisir le comité, puis son responsable, donne $k\binom nk$. Choisir d’abord le responsable, puis $k-1$ membres parmi les $n-1$ autres personnes, donne $n\binom{n-1}{k-1}$. Donc

$$k\binom nk=n\binom{n-1}{k-1}.$$

Pour un comité de trois personnes choisies parmi huit, avec un responsable désigné, les deux méthodes donnent $3\binom83=8\binom72=168$. Les objets comptés sont des comités avec un membre marqué. Compter seulement les comités omet les trois choix possibles du responsable dans chacun.

Répétition et objets indiscernables

Répartir des unités identiques : étoiles et séparateurs

Reprenons le problème initial. Les unités sont identiques, les trois équipes sont distinctes et chacune peut recevoir zéro unité, sans limite de capacité. On compte les solutions entières non négatives de

$$x_1+x_2+x_3=7.$$

Sept étoiles représentent les unités, et deux séparateurs délimitent les trois équipes : **|***|** représente $(2,3,2)$. Des séparateurs adjacents autorisent une équipe centrale vide ; un séparateur à une extrémité autorise une équipe d’extrémité vide. Chaque triplet détermine une seule chaîne, et chaque chaîne permet de retrouver un seul triplet.

Il suffit donc de choisir les deux positions des séparateurs parmi neuf positions, soit $\binom92=36$ répartitions. En général, répartir $r\ge0$ objets identiques dans $b\ge1$ boîtes distinctes, en autorisant les boîtes vides et sans plafond de capacité, donne $\binom{r+b-1}{b-1}$ résultats. Les notes de CS70 utilisent cette correspondance pour le tirage avec remise lorsque l’ordre ne compte pas.

Si chaque équipe doit recevoir au moins une unité, on en attribue d’abord une à chacune, puis on répartit les quatre restantes : $\binom62=15$. Avec des objets distincts, le problème initial aurait $3^7=2187$ résultats. Si les équipes sont elles aussi indiscernables, plusieurs positions des séparateurs peuvent décrire la même répartition ; il faut changer de modèle.

Ordonner un multiensemble fixé

Dans AABC, les deux exemplaires de A sont indiscernables. Numérotons-les temporairement : les quatre objets distincts ont $4!$ permutations. En effaçant les numéros, exactement $2!$ permutations numérotées donnent chaque arrangement visible. Il y a donc $4!/2!=12$ résultats.

Plus généralement, si $n$ valeurs ont pour multiplicités $m_1,\ldots,m_t$, avec $\sum_i m_i=n$, le nombre de suites distinctes vaut

$$\frac{n!}{m_1!\cdots m_t!}.$$

La section 14.6 du MIT donne cette règle. La division est justifiée parce que chaque arrangement visible possède le même nombre de versions numérotées. Pour éliminer ces branches répétées pendant la recherche, voir les permutations par retour arrière.

Ensembles qui se recouvrent : inclusion–exclusion

Le principe d’inclusion–exclusion de la section 14.9 du MIT corrige les recouvrements dans une union d’ensembles finis. Pour deux ensembles, $|A\cup B|=|A|+|B|-|A\cap B|$. Pour trois,

$$\begin{aligned} |A\cup B\cup C|={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

Un élément présent dans les trois ensembles est ajouté trois fois, puis soustrait trois fois ; il faut donc l’ajouter une dernière fois. Pour davantage d’ensembles, on poursuit en alternant les signes selon le nombre d’ensembles participant à chaque intersection, jusqu’au dernier niveau.

Exemple résolu : filtrer les entiers de 1 à 100

Combien d’entiers de 1 à 100 inclus ne sont divisibles par aucun des nombres 2, 3 ou 5 ? Posons $U=\{1,\ldots,100\}$, et notons $A,B,C$ les ensembles de ses multiples de 2, 3 et 5 respectivement.

Ensemble	Condition d’appartenance	Nombre
$A$	Multiple de 2	$\lfloor100/2\rfloor=50$
$B$	Multiple de 3	$\lfloor100/3\rfloor=33$
$C$	Multiple de 5	$\lfloor100/5\rfloor=20$
$A\cap B$	Multiple de 6	16
$A\cap C$	Multiple de 10	10
$B\cap C$	Multiple de 15	6
$A\cap B\cap C$	Multiple de 30	3

Les intersections sont déterminées par le plus petit commun multiple des diviseurs concernés. Il n’est égal à leur produit que si ces diviseurs sont premiers entre eux deux à deux. Ainsi,

$$|A\cup B\cup C|=50+33+20-16-10-6+3=74.$$

Ces entiers sont ceux à exclure. La réponse est donc $|U|-74=100-74=26$. On peut énumérer directement les ensembles avec Python 3 :

U = set(range(1, 101))
A = {x for x in U if x % 2 == 0}
B = {x for x in U if x % 3 == 0}
C = {x for x in U if x % 5 == 0}
union_count = (len(A) + len(B) + len(C)
               - len(A & B) - len(A & C) - len(B & C)
               + len(A & B & C))
valid = U - (A | B | C)
assert union_count == len(A | B | C)
print(union_count, len(valid))
print(sorted(valid))

Sortie :

74 26
[1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97]

Principe des tiroirs et impossibilité

Le principe des tiroirs répartit des objets entre un nombre fini de catégories : si chacun des $N$ objets est placé dans l’une de $b\ge1$ boîtes, l’une des boîtes contient au moins $\lceil N/b\rceil$ objets. La section 14.8 du MIT l’énonce comme une propriété des fonctions : une application d’un ensemble plus grand vers un ensemble plus petit ne peut pas être injective.

Par exemple, répartir 17 tâches entre cinq exécutants oblige l’un d’eux à en recevoir au moins quatre. Si chacun en recevait au plus trois, la capacité totale serait seulement de $5\times3=15$, insuffisante pour 17 tâches.

De même, toute fonction déterministe qui associe à chaque chaîne binaire de neuf bits une chaîne de huit bits produit une collision : elle a $2^9=512$ entrées pour seulement $2^8=256$ sorties. Elle ne peut pas posséder d’inverse unique pour toutes ses entrées. La preuve garantit l’existence d’une paire en collision, sans préciser laquelle ni le coût de sa recherche.

Espaces de recherche et bornes inférieures

Le dénombrement permet d’estimer le nombre de candidats à examiner. Les 36 répartitions entre trois équipes peuvent être comptées par étoiles et séparateurs, ou trouvées en énumérant des triplets :

from itertools import product
from math import comb

allocations = [x for x in product(range(8), repeat=3) if sum(x) == 7]
assert len(allocations) == comb(9, 2)
print(len(allocations), allocations[:5])

Sortie :

36 [(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4), (0, 4, 3)]

Ce code examine $8^3=512$ triplets pour en retenir 36. Le nombre de candidats, le nombre de résultats valides et le temps d’exécution demandent des calculs distincts. L’élagage modifie le nombre de nœuds visités, et traiter un nœud peut demander un travail supplémentaire.

Si la tâche exige de produire explicitement $M$ suites de longueur $\ell$, en écrivant tous les éléments de chacune, le temps de sortie est au moins $\Omega(M\ell)$ dans un modèle où écrire un élément a un coût constant. Conserver simultanément tous les résultats sous forme de listes séparées exige également au moins $\Omega(M\ell)$ d’espace. Dix valeurs distinctes ont $10!=3628800$ permutations ; les produire intégralement demande d’écrire 36288000 éléments. Une production progressive réduit le stockage simultané, mais conserve toutes ces écritures. Calculer seulement le nombre de résultats est une autre tâche.

Une autre borne vient du nombre de cas à distinguer. Si un algorithme déterministe distingue $M\ge1$ cas uniquement par des questions ayant chacune au plus $q\ge2$ réponses possibles, son arbre de décision de profondeur $h$ possède au plus $q^h$ feuilles. Ainsi, $h\ge\lceil\log_q M\rceil$. Pour trier par comparaisons des clés distinctes quelconques, $M=n!$ et chaque comparaison entre clés distinctes a $q=2$ résultats. C’est l’argument par arbre de décision d’Open Data Structures, section 11.1.4. Les $8!=40320$ ordres relatifs de huit clés distinctes exigent au moins 16 comparaisons dans le pire cas, car $2^{15}<40320\le2^{16}$.

La borne de sortie compte ce qu’il faut écrire ; la borne par arbre de décision compte l’information nécessaire pour distinguer les cas. Elles permettent d’évaluer la possibilité d’énumérer tous les résultats plus vite ou de décider avec moins de questions. La carte des algorithmes de tri précise le domaine du modèle par comparaisons et explique pourquoi une structure supplémentaire des clés permet d’autres méthodes de tri.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.