Atelier de combinatoire

Calculateur de combinaisons et permutations

Calcule nCr et nPr, les répétitions, étoiles et barres, permutations de multiensembles, répartitions, inclusion-exclusion, dérangements et chemins sur grille.

Exemple résolu — Atelier de combinatoire

Compte exact	120
Approx.	120
Chiffres	3
log10	2,0792

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Théorie du dénombrement — cas par cas

Deux questions par oui ou non classent tout problème de dénombrement

Choisir (sans répétition) C(n,k) = n! / (k!(n − k)!)

Arranger (sans répétition) P(n,k) = n! / (n − k)!

Ordonné avec répétition n^k

Choisir avec répétition C(n + k − 1, k)

Choisir (sans répétition)

Formule: C(n,k) = n! / (k!(n − k)!)

Exemple détaillé: Choisir 3 personnes parmi 10. Comme l’ordre ne compte pas, C(10,3) = 120 comités.

Ouvrir cet exemple: choix de comité

Choisir (sans répétition). Sélection non ordonnée : les jetons sélectionnés forment un ensemble, pas une séquence. Choisir 3 personnes parmi 10 : l'ordre n'a pas d'importance. — Sélection non ordonnée : les jetons sélectionnés forment un ensemble, pas une séquence.

Arranger (sans répétition)

Formule: P(n,k) = n! / (n − k)!

Exemple détaillé: Attribuer l’or, l’argent et le bronze parmi 10 finalistes. Comme les rôles diffèrent, P(10,3) = 720 podiums possibles.

Ouvrir cet exemple: ordre du podium

Arranger (sans répétition). Emplacements ordonnés : échanger les positions crée un nouveau résultat. Podium des 3 premiers parmi 10 : l'ordre compte. — Emplacements ordonnés : échanger les positions crée un nouveau résultat.

Ordonné avec répétition

Formule: n^k

Exemple détaillé: Former un code PIN à 4 chiffres parmi 10 chiffres. L’ordre compte et les chiffres peuvent se répéter : 10^4 = 10 000 codes.

Ouvrir cet exemple: code PIN

Ordonné avec répétition. Chaque emplacement choisit indépendamment dans le même ensemble. Code PIN à 4 chiffres : répétition autorisée. — Chaque emplacement choisit indépendamment dans le même ensemble.

Choisir avec répétition

Formule: C(n + k − 1, k)

Exemple détaillé: Choisir 3 boules parmi 8 parfums, en ignorant l’ordre et en autorisant les répétitions. C(10,3) = 120 multi-ensembles de parfums.

Ouvrir cet exemple: boules de glace

Choisir avec répétition. Étoiles et barres : les séparateurs codent les choix répétés. 3 boules parmi 8 parfums : ordre ignoré, répétitions autorisées. — Étoiles et barres : les séparateurs codent les choix répétés.

Permutation de multi-ensemble

Formule: N! / (n₁! · n₂! · … · n_r!)

Exemple détaillé: MISSISSIPPI contient 11 lettres : I×4, S×4, P×2 et M×1. Après division des échanges identiques, 11!/(4!4!2!) = 34 650 arrangements.

Ouvrir cet exemple: MISSISSIPPI

Permutation de multi-ensemble. Les symboles répétés divisent le total des permutations par les échanges de doublons. Onze lettres, quatre S, quatre I, deux P : 11! sur 4!·4!·2! = 34 650. Sans les répétitions, le résultat atteindrait 39 916 800. Ces doublons éliminent ainsi plus de 99,9 % des arrangements possibles.. — Les symboles répétés divisent le total des permutations par les échanges de doublons.

Boules dans des urnes

Formule: Σ_i=0^m (−1)ⁱC(m,i)(m − i)ⁿ

Exemple détaillé: Attribuer 6 tâches distinctes à 3 personnes nommées, sans laisser personne sans tâche. L’inclusion–exclusion donne 3^6 − 3·2^6 + 3 = 540 attributions.

Ouvrir cet exemple: distinctes vers urnes (surjective)

Boules dans des urnes. Vue boules et urnes pour les contraintes d'attribution/distribution. Répartir 6 tâches distinctes entre 3 employés, chacun en reçoit au moins une. — Vue boules et urnes pour les contraintes d'attribution/distribution.

Inclusion-exclusion

Formule: C(n,k) − C(b,k)

Exemple détaillé: Choisir une main non ordonnée de 5 cartes contenant au moins un As. C(52,5) − C(48,5) = 886 656 mains.

Ouvrir cet exemple: au moins un As

Inclusion-exclusion. Représentation des chevauchements d'ensembles pour le comptage par addition-soustraction. Main de 5 cartes avec au moins un As, par dénombrement du complémentaire. — Représentation des chevauchements d'ensembles pour le comptage par addition-soustraction.

Cas particuliers

Formule: !n = n! Σ_i=0ⁿ (−1)ⁱ / i!

Exemple détaillé: Attribuer 8 noms au Père Noël secret sans auto-tirage. Le nombre de dérangements est !8 = 14 833.

Ouvrir cet exemple: père noël secret

Cas particuliers. Comptages classiques sous contrainte : circulaire, dérangement et chemins en grille. Huit personnes, aucune ne tirant son propre nom : 14 833 possibilités. C'est 8! divisé par e et arrondi. Le nombre de dérangements est toujours l'entier le plus proche de n!/e. C'est de là que vient le troisième bloc d'observations ci-dessous.. — Comptages classiques sous contrainte : circulaire, dérangement et chemins en grille.

Références (1)

The last case in the guide above is Secret Santa, and insight block 3 finds e hiding in it. That is the matching problem, and it is three centuries old: P. Gorroochurn, "Rencontres with Montmort (1708)", chapter 7 of Classic Problems of Probability, 54–61. Wiley, 2012 — the probability that nobody draws their own name tends to 1/e.

Exercice

Vérifiez-vous

Prédisez d’abord la réponse, puis utilisez les commandes ci-dessus pour vérifier. N’affichez la solution qu’après vous être engagé sur une hypothèse : c’est ce qui en fait un exercice.

Choisissez 3 personnes parmi 10 pour un comité. Puis désignez les 1re, 2e et 3e places parmi les mêmes 10. Même n, même k — les deux comptes diffèrent-ils, et si oui d’exactement quel facteur ? Vérifiez avec les deux premiers modèles.

Afficher la réponse

120 contre 720, un facteur 6. Une seule question les sépare, et ce ne sont pas les nombres : l’ordre compte-t-il ? Chaque comité non ordonné de 3 peut être aligné en 3! = 6 podiums différents ; arranger, c’est donc toujours choisir multiplié par k!. Le facteur vaut k! et jamais autre chose, et c’est pourquoi les deux formules ne diffèrent que par cette unique division.
Un code PIN à 4 chiffres tiré de 10 chiffres, et 4 boules de glace choisies parmi 10 parfums où un parfum peut se répéter. Les deux autorisent la répétition. Prédisez quel compte est le plus grand, puis vérifiez.

Afficher la réponse

10,000 contre 715. La répétition est permise dans les deux cas : ce n’est donc pas elle qui les sépare, c’est l’ordre. Le PIN est ordonné avec répétition, n^k = 10⁴. Les boules sont non ordonnées avec répétition, C(n + k − 1, k) = C(13,4) = 715. Les deux modèles « avec répétition » sont aussi éloignés que les deux sans, et c’est pourquoi la question « les éléments peuvent-ils se répéter ? » ne suffit jamais seule. Il en faut toujours deux.
Six prix distincts dans trois boîtes distinctes donnent 729. Changez la variante pour que chaque boîte reçoive au moins un prix et le compte tombe à 540. Où sont passées les 189 répartitions manquantes ?

Afficher la réponse

Ce sont exactement les répartitions qui laissent une boîte vide, et les compter exige une somme alternée plutôt qu’une formule. On choisit la boîte vide de 3 façons et on remplit le reste de 2⁶ = 64 façons : 3 × 64 = 192. Mais les 3 cas où les six prix atterrissent dans une seule boîte y ont été comptés deux fois, il faut donc retrancher 3. Restent 192 − 3 = 189 répartitions à boîte vide, et 729 − 189 = 540. C’est le seul modèle de l’atelier dont la réponse est une somme alternée : le plus lent à calculer, et le plus facile à rater à la main.

Problèmes entièrement résolus

Choisir 3 parmi 10 et la réponse pour choisir 7 5 étapes
Choisir 3 éléments parmi 10 donne 120 possibilités. Déduisez-le du dénombrement ordonné, puis expliquez pourquoi 120 est aussi la réponse pour le choix de 7.
1. Comptez d'abord les sélections ordonnées, car elles sont plus simples : dix choix, puis neuf, puis huit.
  
  $P (10, 3) = 10 \times 9 \times 8 = 720 = 3! (3 10)$
2. Cela compte chaque ensemble de trois éléments plusieurs fois — une fois pour chaque ordre dans lequel ces trois mêmes éléments peuvent apparaître, soit 3! = 6.
3. La division donne 120, et la division par k! constitue toute la différence entre une permutation et une combinaison.
  
  $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$
4. La symétrie découle du sens même du choix. Choisir 3 éléments à prendre revient au même que choisir 7 éléments à laisser, de sorte que les deux décomptes ne peuvent différer.
  
  $(3 10) = (7 10) = 120 (choosing 3 is choosing which 7 to omit)$
5. Le log₁₀ de 2,0792 sur le panneau est le complément pratique : trois chiffres. Pour un grand n, le nombre dépasse tout ce qu'on peut conserver, et le logarithme est ce qui reste calculable.
  
  $lo g_{10} 120 = 2.0792 ⟹ 3 digits$
Réponse

L'outil affiche 120, 3 chiffres et log₁₀ = 2,0792. La symétrie mérite d'être assimilée car elle divise le travail par deux : personne ne devrait calculer C(10, 7) à partir de zéro. Et toute la ligne a pour somme 2¹⁰ = 1024 — chaque sous-ensemble de dix éléments, compté par taille — ce qui constitue la vérification de cohérence la plus rapide pour tout calcul binomial que vous aurez à effectuer. La valeur la plus grande est C(10, 5) = 252, de sorte que le milieu de la ligne contient environ un quart de tous les sous-ensembles, tandis que les deux extrémités en contiennent un chacun.

$(k n) = \frac{P ( n , k )}{k !} : order costs a factor of k! = 6$
Les 2 598 960 façons de distribuer une main de cinq cartes pour une couleur 5 étapes
Une main de cinq cartes peut être distribuée de 2 598 960 façons. Construisez ce résultat à partir du tirage ordonné, puis utilisez-le pour évaluer une couleur. Il s'agit de Choisir (sans répétition) avec n = 52 et k = 5.
1. Distribuez d'abord dans l'ordre. La première carte offre 52 possibilités, la suivante 51, et ainsi de suite jusqu'à 48 — soit cinq facteurs, sans division pour l'instant.
  
  $P (52, 5) = 52 \times 51 \times 50 \times 49 \times 48 = 311875200$
2. Une main est un ensemble, et le décompte ordonné a compté chaque ensemble 120 fois, une fois pour chaque ordre dans lequel les mêmes cinq cartes auraient pu arriver. Diviser par 5! est la seule étape qui transforme une distribution en une main.
  
  $(5 52) = \frac{311 875 200}{5 !} = \frac{311 875 200}{120} = 2598960$
3. Comptez maintenant les couleurs au sein de cet espace : choisissez la couleur de quatre manières, puis cinq des treize cartes de cette couleur.
  
  $flushes = 4 (5 13) = 4 \times 1287 = 5148$
4. Ce qui explique la rareté d'une couleur. Ce n'est pas que 5 148 soit un petit nombre de mains — c'est que l'espace au sein duquel il se situe est cinq cents fois plus grand.
  
  $P (flush) = \frac{5148}{2 598 960} = 0.00198 \approx \frac{1}{505}$
5. Et cet espace reste suffisamment réduit pour être concret. À raison d'une main par seconde, sans s'arrêter, chaque main distincte aura été distribuée en moins d'un mois.
  
  $\frac{2 598 960}{86 400} = 30.1 days, at one hand per second$
Réponse

L'outil affiche 2 598 960, 7 chiffres et log₁₀ = 6,4148. La hiérarchie des mains au poker repose sur cette arithmétique et rien d'autre. Comptez les suites de la même manière — dix hauteurs de départ, quatre couleurs pour chacune des cinq cartes, 10 × 4⁵ = 10 240 — et il y a deux fois plus de suites que de couleurs, ce qui explique exactement pourquoi une couleur bat une suite. Ce classement n'a pas été conçu ; il a été compté.

$(5 52) = 2598960 P (flush) \approx \frac{1}{505}$
Les 62 990 928 000 formes d'un mot de passe de huit lettres sans lettre répétée 5 étapes
Un mot de passe de huit lettres sans lettre répétée compte 62 990 928 000 formes. Dénombrez-le, puis dénombrez le même mot de passe sans cette règle, et décidez lequel vous préféreriez défendre. Il s'agit de Arranger (sans répétition) avec n = 26 et k = 8.
1. Remplissez les emplacements de gauche à droite. Le premier prend l'une des 26 lettres ; le second en prend 25, car la lettre utilisée a disparu.
  
  $P (26, 8) = \frac{26 !}{18 !} = 26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19$
2. Huit facteurs décroissants, et ce produit constitue toute la réponse. Il s'agit d'un arrangement plutôt que d'une combinaison, car l'ordre des lettres est le mot de passe.
  
  $= 62990928000$
3. Supprimez maintenant la règle. Chaque emplacement est à nouveau indépendant et chacun dispose des 26 lettres, le décompte est donc une simple puissance.
  
  $2 6^{8} = 208827064576 (repeats allowed)$
4. La comparaison fait tout l'intérêt : interdire les répétitions ne conserve que 30,2 % des chaînes. Une règle qui ressemble à un renforcement a éliminé sept chaînes sur dix.
  
  $\frac{62 990 928 000}{208 827 064 576} = 0.302$
5. En temps d'attaque, à raison d'un milliard de tentatives par seconde, les deux espaces représentent une minute et trois minutes et demie. Ni l'un ni l'autre ne constitue une défense — et la règle a rendu le plus court encore plus court.
  
  $1 0^{9} guesses/s : 63 s vs 209 s$
Réponse

Avec n = 26, k = 8 et le modèle réglé sur Arranger (sans répétition), l'outil affiche 62 990 928 000, 11 chiffres et log₁₀ = 10,7993. Chaque règle de composition réduit l'espace, sans exception, car une règle ne peut qu'interdire. Qu'elle soit justifiée dépend de quelque chose que cette arithmétique ne peut voir : si les chaînes qu'elle interdit sont celles que les gens choisissent bien plus souvent que par hasard. Bannir un mot de passe tristement célèbre coûte une chaîne. Bannir toutes les lettres répétées en coûte 145 836 136 576.

$P (26, 8) = 0.302 \times 2 6^{8} : forbidding repeats deletes 69.8% of the strings$
Trois tentatives à un distributeur pour un code PIN à quatre chiffres 5 étapes
Un code PIN à quatre chiffres compte 10 000 valeurs. Déterminez ce que valent trois tentatives à un distributeur automatique, et ce que coûte réellement le conseil classique d'éviter les chiffres répétés. Il s'agit de Ordonné avec répétition avec n = 10 et k = 4.
1. Quatre emplacements, dix chiffres dans chacun, et rien ne les relie — le chiffre que vous venez d'utiliser reste disponible pour l'emplacement suivant.
  
  $10 \times 10 \times 10 \times 10 = 1 0^{4} = 10000$
2. Trois tentatives face à un code PIN choisi uniformément représentent donc trois chances sur dix mille. La limite de trois essais n'est pas une amélioration par rapport à des essais illimités ; face à cet espace, elle constitue l'intégralité de la défense.
  
  $3 attempts : \frac{3}{10 000} = 0.03%$
3. Imposez maintenant la règle sans chiffre répété : dix choix, puis neuf, puis huit, puis sept.
  
  $no repeated digit : 10 \times 9 \times 8 \times 7 = 5040$
4. La règle conserve 5 040 codes PIN et en détruit 4 960. La moitié de l'espace a disparu — et la moitié éliminée incluait 1111 avec tout le reste.
  
  $\frac{5040}{10 000} = 0.504$
5. Deux chiffres supplémentaires ne représentent pas deux essais de plus. Chaque chiffre multiplie par dix, un code PIN à six chiffres représente donc un espace cent fois plus grand.
  
  $six digits : 1 0^{6} = 1000000 = 100 \times 1 0^{4}$
Réponse

L'outil affiche 10 000 pour n = 10, k = 4. Les deux faits sont vrais simultanément : l'espace est minuscule, et un code PIN convient généralement très bien malgré tout — parce que la limite de trois tentatives n'accorde à un attaquant que 0,03 % de cet espace au lieu de la totalité. Changez la menace et la réponse s'inverse. Un fichier de codes PIN volé n'a pas de limite d'essais, et dix mille candidats représentent une fraction de seconde de travail, c'est pourquoi la sécurité d'un code PIN ne repose jamais sur le seul code PIN.

$n^{k} = 1 0^{4} = 1000010 \times 9 \times 8 \times 7 = 5040$
Trois boules parmi huit parfums et trois personnes parmi dix 5 étapes
Trois boules parmi huit parfums, avec répétitions autorisées, font 120 — soit le même nombre que choisir trois personnes parmi dix. Montrez que ce n'est pas une coïncidence. Il s'agit de Combinaison avec répétition avec n = 8 et k = 3.
1. Écrivez la commande sous la forme d'une rangée de symboles : une étoile pour chaque boule, une barre pour chaque passage au parfum suivant. Trois boules parmi huit parfums nécessitent trois étoiles et sept barres.
  
  $3 scoops ⋆ ⋆ ⋆ and 7 bars ∣ ∣ ∣ ∣ ∣ ∣ ∣$
2. Chaque disposition de ces dix symboles correspond à une commande, et chaque commande à une disposition. La question revient donc seulement à savoir quelles 3 des 10 positions occupent les étoiles — ce qui est la question du problème 1 avec des noms différents.
  
  $(3 3 + 7) = (3 10) = 120$
3. Interdisez les répétitions et le décompte tombe à 56. L'autorisation de répéter un parfum vaut 64 commandes supplémentaires, ce qui fait plus que doubler le menu.
  
  $(3 8) = 56 (no repeats allowed)$
4. Faites maintenant en sorte que l'ordre compte également, de sorte que vanille-vanille-menthe diffère de menthe-vanille-vanille : huit choix indépendants, trois fois de suite.
  
  $8^{3} = 512 (ordered, repeats allowed)$
5. Le rapport entre ces deux nombres est de 4,27, et non 3! = 6. Un cornet comportant une boule répétée possède moins d'ordonnancements distincts qu'un cornet avec trois boules différentes, de sorte que diviser par 3! est exactement l'étape à ne pas effectuer ici.
  
  $\frac{512}{120} = 4.27 \neq = 3! = 6$
Réponse

L'outil affiche 120, 3 chiffres et log₁₀ = 2,0792 — le même résultat que pour le problème 1, issu d'une question différente. Les étoiles et barres sont une traduction plutôt qu'une formule : elles transforment la répétition en position, là où vous savez déjà quoi faire. Le piège tendu se situe à l'étape 5. Une fois les répétitions autorisées, les ordonnancements cessent d'être interchangeables, et aucun facteur unique ne permet de passer du décompte ordonné au décompte non ordonné.

$(k n + k - 1) : k stars, n - 1 bars$
Les 34 650 mots distincts de MISSISSIPPI avec quatre S s'évitant 5 étapes
Les lettres de MISSISSIPPI forment 34 650 mots distincts. Démontrez-le, puis répondez à une question plus difficile pour laquelle l'outil n'a pas de champ : à quelle fréquence les quatre S s'évitent-ils ? Il s'agit de Permutation de multiensemble avec des effectifs de 1, 4, 4, 2.
1. Commencez par faire comme si chaque lettre était distinguable — numérotez les S de S₁ à S₄. C'est alors une simple permutation de onze objets.
  
  $11! = 39916800$
2. Retirez maintenant les numéros. Les quatre S peuvent être permutés de 4! façons sans changer ce qui est écrit, et il en va de même pour les quatre I et les deux P, de sorte que chaque mot visible a été compté 1 152 fois.
  
  $\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1152} = 34650$
3. Ce qui donne directement une probabilité : mélangez les onze jetons et une disposition sur 34 650 forme le nom de l'État.
  
  $P (a shuffle spells MISSISSIPPI) = \frac{1}{34 650} = 0.0000289$
4. Pour la question plus difficile, placez d'abord les sept autres lettres — M, quatre I, deux P — et comptez leurs dispositions. Cela laisse huit interstices en comptant les deux extrémités, et chaque S doit occuper un interstice différent.
  
  $\frac{7 !}{1 ! 4 ! 2 !} = 105, (4 8) = 70$
5. Multipliez et divisez : 7 350 des 34 650 mots maintiennent les S séparés, soit 21,2 %.
  
  $\frac{105 \times 70}{34 650} = \frac{7350}{34 650} = 0.2121 = \frac{7}{33}$
Réponse

L'outil affiche 34 650, 5 chiffres et log₁₀ = 4,5397. La méthode des interstices des étapes 4 et 5 a plus de valeur que la réponse elle-même. C'est la démarche générale pour toute condition du type pas deux d'entre eux côte à côte : placez les éléments sans contrainte, puis choisissez les interstices pour les éléments contraints. La contiguïté est une condition qu'aucune factorielle ne peut exprimer, et les interstices la transforment en un choix de positions — soit la seule chose que chaque formule de cette page sait déjà compter.

$\frac{n !}{n _{1} ! n _{2} ! \dots} : divide by the orderings you cannot see$
Six tâches distinctes confiées à trois travailleurs sans laisser personne inactif 5 étapes
Six tâches distinctes confiées à trois travailleurs sans que personne ne reste inactif font 540 affectations. Démontrez-le en éliminant les mauvais cas plutôt qu'en comptant les bons. Il s'agit de Boules dans des urnes, objets distincts, chaque urne utilisée, avec n = 6 et m = 3.
1. Ignorez d'abord la contrainte. Chaque tâche choisit indépendamment l'un des trois travailleurs, de sorte que le décompte sans restriction est une puissance — et il est beaucoup plus simple que le décompte avec restriction.
  
  $3^{6} = 729 (no restriction)$
2. Soustrayez maintenant les affectations qui laissent quelqu'un sans rien : choisissez le travailleur inactif de trois façons, puis donnez les six tâches aux deux autres.
  
  $one worker idle : (1 3) 2^{6} = 3 \times 64 = 192$
3. Cette soustraction est allée trop loin. Une affectation n'utilisant qu'un seul travailleur a été soustraite deux fois, une fois pour chaque collègue qu'elle laissait inactif, donc ces trois-là sont réajoutées.
  
  $two idle, added back : (2 3) 1^{6} = 3$
4. L'alternance de soustractions et d'additions est le principe d'inclusion-exclusion, et la somme alternée est ce qu'affiche la ligne de formule de l'outil.
  
  $729 - 192 + 3 = 540$
5. Ainsi, trois quarts de toutes les affectations utilisent tout le monde. Divisez par 3! pour rendre les travailleurs interchangeables et vous obtenez S(6, 3) = 90, le nombre de Stirling de deuxième espèce — les mêmes partitions, comptées sans noms.
  
  $\frac{540}{729} = 0.7407, S (6, 3) = \frac{540}{3 !} = 90$
Réponse

L'outil affiche 540, 3 chiffres et log₁₀ = 2,7324. L'étape 3 est celle où ce problème se perd habituellement. L'instinct veut que la soustraction des mauvais cas soit la méthode, mais ce n'est pas le cas : la soustraction sur des ensembles qui se chevauchent va toujours trop loin, et les termes de correction ne sont pas là pour faire joli. Le 90 de l'étape 5 est le même objet sous un autre angle — avec des travailleurs nommés, il y a 540 affectations, sans noms, 90 partitions, et l'écart entre les deux correspond exactement aux 3! façons d'attribuer les noms.

$i = 0 \sum m (- 1)^{i} (i m) (m - i)^{n} = 540 = 3! S (6, 3)$
Douze jetons identiques dans quatre boîtes étiquetées avec aucune de vide 5 étapes
Douze jetons identiques dans quatre boîtes étiquetées sans aucune boîte vide donne 165. Y parvenir en satisfaisant la contrainte au préalable. Il s'agit du modèle Boules et urnes, objets identiques, aucune urne vide, avec n = 12 et m = 4.
1. La contrainte exige que chaque boîte en reçoive au moins un ; satisfaisons-la immédiatement : on dépose un jeton dans chaque boîte et on n'a plus à s'en soucier. Il reste huit jetons, et il n'y a désormais plus aucune règle.
  
  $pay the floor first : 12 - 4 = 8 units still free$
2. Répartir librement des objets identiques relève de la méthode des étoiles et des barres — huit étoiles, trois barres pour séparer quatre boîtes — et le dénombrement revient à choisir l'emplacement des barres.
  
  $(4 - 1 8 + 4 - 1) = (3 11) = 165$
3. En supprimant la règle d'absence de boîte vide, la même méthode donne 455, car les douze jetons sont alors tous libres.
  
  $without the floor : (3 12 + 4 - 1) = (3 15) = 455$
4. Ainsi, le minimum d'un jeton élimine près des deux tiers des répartitions : seules 165 sur les 455 y survivent.
  
  $\frac{165}{455} = 0.363$
5. Si l'on rend au contraire les jetons discernables, le dénombrement passe à 16 777 216. L'indiscernabilité coûte cher — cinq ordres de grandeur, pour douze objets.
  
  $distinct units instead : 4^{12} = 16777216$
Réponse

L'outil affiche 165, 3 chiffres et log₁₀ = 2,2175. L'étape 1 constitue la méthode généralisable : une borne inférieure sur chaque part peut être réglée d'avance, car la payer laisse un problème de même forme avec un n plus petit. Porter le minimum à trois chacun laisse douze moins douze, de sorte que la réponse vaut un. Cela ne fonctionne pas vers le haut, et cette dissymétrie est toute la raison pour laquelle au plus deux par boîte est une question plus difficile qu'au moins un.

$(m - 1 n - 1) : a floor of one is a constant, not a new formula$
Les 886 656 mains de cinq cartes contenant au moins un as 5 étapes
886 656 mains de cinq cartes contiennent au moins un as. Dénombrer les mains qui n'en contiennent pas et soustraire — puis reconstruire le même nombre par la méthode longue en guise de vérification. Il s'agit du principe d'Inclusion-Exclusion, au-moins-un, avec n = 52, k = 5 et 48 cartes qui ne sont pas des as.
1. Dénombrer directement les mains ayant au moins un as implique de séparer les cas à un, deux, trois et quatre as. Dénombrer le complémentaire ne demande qu'un seul calcul, il convient donc de commencer par là.
  
  $(5 52) = 2598960$
2. Une main sans aucun as est formée de cinq cartes tirées parmi les 48 cartes qui ne sont pas des as.
  
  $(5 48) = 1712304 (not one ace)$
3. En soustrayant, chaque main restante contient au moins un as — car une main ne contient soit aucun as, soit au moins un, sans intermédiaire.
  
  $2598960 - 1712304 = 886656$
4. Ainsi, un tiers de l'ensemble des mains contient au moins un as, ce qui est bien plus élevé que ne le suggère l'expression quatre as dans cinquante-deux cartes.
  
  $P = \frac{886 656}{2 598 960} = 0.3412$
5. Passons à la vérification. Dénombrer exactement un as, exactement deux, exactement trois et exactement quatre, puis faire la somme. Quatre calculs distincts, et le total concorde au dernier chiffre près.
  
  $4 (4 48) + 6 (3 48) + 4 (2 48) + (1 48) = 778320 + 103776 + 4512 + 48 = 886656$
Réponse

L'outil affiche 886 656, 6 chiffres et log₁₀ = 5,9478. L'étape 5 n'est pas de la décoration. Au moins un est la formulation le plus souvent dénombrée sous la forme 4 × C(48, 4) = 778 320 — choisir un as, puis compléter autour — et ce nombre est faux car une main contenant deux as est produite deux fois par cette formule, une fois à partir de chacun de ses as. Le complémentaire ne peut jamais commettre cette erreur, c'est pourquoi c'est le premier réflexe à avoir dès qu'une question comporte l'expression au moins un.

$∣ A ∣ = N - ∣ A^{c} ∣ : count the easy side and subtract$
Quarante, trente-cinq et vingt-huit membres répartis dans trois clubs 5 étapes
Quarante, trente-cinq et vingt-huit membres répartis dans trois clubs ne font pas 103 personnes. Trouver l'effectif réel, puis le répartir entre les personnes appartenant à un seul club, à deux clubs ou aux trois. Il s'agit du principe d'Inclusion-Exclusion, union de trois ensembles, avec des recouvrements deux à deux de 12, 10 et 9 et un triple recouvrement de 4.
1. Additionnons les trois effectifs. Toute personne inscrite dans deux clubs a été comptée deux fois, et toute personne inscrite dans les trois a été comptée trois fois, de sorte que 103 est une borne supérieure et rien de plus.
  
  $40 + 35 + 28 = 103$
2. Soustrayons chaque recouvrement deux à deux. Une personne appartenant à exactement deux clubs est désormais comptée correctement — mais une personne appartenant aux trois clubs a été comptée trois fois et soustraite trois fois, de sorte qu'elle a complètement disparu.
  
  $103 - (12 + 10 + 9) = 103 - 31 = 72$
3. Réadditionnons le triple recouvrement pour les réintégrer. C'est là tout le principe d'inclusion-exclusion pour trois ensembles : ajouter les simples, soustraire les paires, ajouter le triple.
  
  $72 + ∣ A \cap B \cap C ∣ = 72 + 4 = 76$
4. L'union ne dit pas comment ces 76 personnes sont réparties, mais les trois mêmes données permettent aussi de répondre à cela. Pondérons les paires par deux et le triple par trois pour retrancher toutes les personnes ayant plus d'une adhésion.
  
  $exactly one = 103 - 2 (31) + 3 (4) = 53$
5. Le reste s'ensuit : 19 personnes appartiennent à exactement deux clubs, et la somme des trois groupes redonne 76.
  
  $exactly two = 31 - 3 (4) = 19, 53 + 19 + 4 = 76$
Réponse

L'outil affiche 76, 2 chiffres et log₁₀ = 1,8808. L'alternance des signes relève d'une correction plutôt que d'un moyen mnémotechnique : chaque terme corrige le dépassement du précédent, et les signes alternent parce que chaque correction dépasse dans l'autre sens. C'est aussi la raison pour laquelle la formule croît si vite — quatre ensembles nécessitent quinze termes, et n ensembles en nécessitent 2ⁿ − 1. Bien avant que cela ne devienne irréalisable, le complémentaire du problème 9 constitue un bien meilleur outil.

$∣ A \cup B \cup C ∣ = Σ_{1} - Σ_{2} + Σ_{3} = 76$
Huit personnes tirant des noms pour un Père Noël secret sans que personne ne tire le sien 5 étapes
Huit personnes tirent au sort pour un Père Noël secret, et 14 833 des 40 320 tirages possibles ne laissent personne avec son propre nom. Établissez ce décompte, puis cherchez combien de personnes tirent habituellement leur propre nom. Il s'agit de Cas particuliers, dérangement, avec n = 8.
1. Un dérangement est une permutation sans point fixe. L'application du principe d'inclusion-exclusion aux huit événements cette personne a tiré son propre nom donne une somme alternée.
  
  $! n = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}$
2. Cette somme correspond aux neuf premiers termes de la série de e⁻¹, et tout ce qu'elle omet est inférieur à 1/9! = 2,8 × 10⁻⁶.
  
  $8! = 40320, i = 0 \sum 8 \frac{( - 1 ) ^{i}}{i !} = 0.367882$
3. Effectuez le calcul et arrondissez : 14 833 tirages dans lesquels personne n'obtient son propre nom.
  
  $! 8 = 40320 \times 0.367882 = 14833$
4. Sous forme de fraction, cela donne 0,36788, contre e⁻¹ = 0,367879 — soit une concordance à cinq décimales près dès huit personnes, qui ne varie presque plus pour des groupes plus grands.
  
  $P = \frac{14 833}{40 320} = 0.36788 \approx e^{- 1} = 0.367879$
5. Passons à une question différente et plus simple. Chaque personne tire son propre nom avec une probabilité de 1/n, et les espérances s'additionnent que les événements soient indépendants ou non ; le nombre espéré d'auto-tirages est donc exactement 1 — pour huit personnes comme pour huit cents.
  
  $E [self-draws] = i = 1 \sum n \frac{1}{n} = n \times \frac{1}{n} = 1$
Réponse

L'outil affiche 14 833, 5 chiffres et log₁₀ = 4,1712. L'étape 5 explique l'étape 4. Si le nombre moyen d'auto-tirages est de 1 quelle que soit la taille du groupe, la probabilité n'en obtenir aucun ne peut pas non plus dépendre fortement de la taille du groupe — et pour un décompte d'événements rares de moyenne 1, cette probabilité vaut e⁻¹. La constante n'est pas ici une simple curiosité. Elle est la réponse à quelle est la probabilité d'obtenir zéro lorsque la moyenne est de un, une question qui revient constantly en dehors de la combinatoire.

$\frac{! n}{n !} \to e^{- 1}, E [self-draws] = 1 for every n$
Chemins les plus courts à travers une grille 7 × 5 avec une case bloquée 5 étapes
442 plus courts chemins traversent une grille 7 × 5 lorsqu'une case est bloquée. Dénombrez-les tous, dénombrez ceux qui passent par la case bloquée, puis soustrayez. Trouvez ensuite la case dont le blocage aurait le plus d'impact. Il s'agit de Cas particuliers, chemin sur réseau, avec 7 pas vers l'est, 5 pas vers le nord et l'obstacle en (3, 2).
1. Tout plus court chemin comporte douze pas, dont sept vers l'est et cinq vers le nord dans un ordre quelconque. Un chemin se résume donc au choix des pas qui vont vers l'est.
  
  $(7 7 + 5) = (7 12) = 792$
2. Un chemin passant par la case bloquée est constitué de deux chemins indépendants raboutés en cette case : du coin à la case, puis de la case au coin opposé. Multipliez, car chaque première moitié s'associe à chaque seconde moitié.
  
  $through (3, 2) : (3 5) (4 7) = 10 \times 35 = 350$
3. Soustrayez, et ce qui reste correspond exactement aux chemins qui évitent cette case.
  
  $792 - 350 = 442$
4. Cette seule case acheminait 44 % de tout le trafic — un seul blocage supprime près de la moitié des chemins.
  
  $\frac{350}{792} = 0.442$
5. Mais ce n'est pas la pire case à perdre. La case située un pas à l'est du départ achemine 462 chemins, soit 58 % d'entre eux, car tout chemin commençant par un pas vers l'est doit nécessairement y passer.
  
  $through (1, 0) : (1 1) (6 11) = 462 = 0.583 of all paths$
Réponse

L'outil affiche 442, 3 chiffres et log₁₀ = 2,6454. L'étape 5 contredit l'impression visuelle. La case bloquée semble causer le plus de dégâts près du centre, là où les chemins paraissent se regrouper ; l'arithmétique indique que les cases proches d'un coin en acheminent davantage, car le nombre de chemins passant par une case est le produit de deux coefficients binomiaux, et près d'un coin, l'un d'eux couvre presque toute la grille. Compter les chemins passant par chaque nœud, plutôt que d'observer la carte, est également la façon dont la redondance est mesurée dans un réseau réel.

$(a a + b) - (x x + y) (a - x ( a - x ) + ( b - y )) = 442$

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Statistiques & Finance →

Exemples de problèmes

choix de comité - Choisir 3 personnes parmi 10 : l'ordre n'a pas d'importance
main de 5 cartes - Une main de poker représente 2 598 960 possibilités, et l'outil affiche à côté l'ordre de grandeur de ce nombre : 7 chiffres, log₁₀ 6,4148. Puis il refuse de les lister. L'espace des résultats est trop vaste pour être énuméré. Ce refus résume toute l'idée. La formule vous livre le total sans jamais construire l'ensemble.
grille de loterie - Six numéros parmi quarante-neuf, ordre ignoré : 13 983 816 tickets. En acheter un chaque semaine exigerait un quart de million d'années pour tous les couvrir. Voilà la façon la plus honnête de lire ces probabilités.
ordre du podium - Podium des 3 premiers parmi 10 : l'ordre compte
mot de passe distinct - Huit lettres sans aucune répétition donnent 62 990 928 000. Soixante-trois milliards obtenus à partir de vingt-six symboles seulement. Interdire les doublons réduit étonnamment peu le total ici, car huit reste modeste par rapport à vingt-six.
arranger tous - Ordonnez les huit éléments. k égale donc n et le calcul donne simplement 8! = 40 320. La formule générale des arrangements se réduit à une factorielle précisément quand aucun élément n'est laissé de côté.
code PIN - Code PIN à 4 chiffres : répétition autorisée
code produit - Six caractères choisis parmi trente-six lettres et chiffres, répétitions autorisées : 2 176 782 336. Deux milliards de codes générés par une étiquette de six caractères. Vous voyez pourquoi les numéros de série sont courts.
boules de glace - 3 boules parmi 8 parfums : ordre ignoré, répétitions autorisées
boules identiques - Douze boules identiques dans cinq urnes distinctes relèvent des étoiles et des barres : C(16, 4) = 1 820. Traiter des objets identiques réduit le compte total au lieu de l'augmenter. En échanger deux ne change absolument rien.
BALLOON - BALLOON a sept lettres, avec deux L et deux O. Le compte est donc de 7! sur 2!·2! = 1 260 au lieu de 5 040. Chaque paire répétée divise le total par deux.
MISSISSIPPI - Onze lettres, quatre S, quatre I, deux P : 11! sur 4!·4!·2! = 34 650. Sans les répétitions, le résultat atteindrait 39 916 800. Ces doublons éliminent ainsi plus de 99,9 % des arrangements possibles.
distinctes vers urnes (quelconque) - Six tâches distinctes pour trois ouvriers sans aucune contrainte. Le choix s'effectue indépendamment pour chaque tâche, d'où 3⁶ = 729. C'est le cas facile. L'exemple suivant, où chacun en reçoit au moins une, marque la fin de cette simplicité.
distinctes vers urnes (surjective) - Répartir 6 tâches distinctes entre 3 employés, chacun en reçoit au moins une
identiques vers urnes (quelconque) - Douze objets identiques dans quatre urnes, vides autorisées : C(15, 3) = 455. Comparez ce résultat avec la version distincte au-dessus. Rendre les objets identiques constitue la réduction la plus drastique de tout le dénombrement.
identiques vers urnes (non vides) - Les douze mêmes objets dans quatre urnes dont aucune ne reste vide : C(11, 3) = 165. Placez d'abord un objet dans chaque urne et distribuez librement les huit restants. Vous comprenez pourquoi la même formule fonctionne avec des nombres plus petits.
au moins un As - Main de 5 cartes avec au moins un As, par dénombrement du complémentaire
union de trois ensembles - Trois clubs de 40, 35 et 28 membres avec des personnes en commun totalisent 76 individus, et non 103. Soustrayez chaque paire une fois et réintégrez le triplet. Les personnes appartenant aux trois clubs avaient été retirées une fois de trop.
table ronde - Asseoir 7 personnes autour d'une table ronde : les rotations sont équivalentes
père noël secret - Huit personnes, aucune ne tirant son propre nom : 14 833 possibilités. C'est 8! divisé par e et arrondi. Le nombre de dérangements est toujours l'entier le plus proche de n!/e. C'est de là que vient le troisième bloc d'observations ci-dessous.
chemin en grille - Les chemins les plus courts sur une grille comportant une case bloquée. Comptez tous les itinéraires, puis soustrayez ceux passant par la case bloquée. C'est tout le principe d'inclusion-exclusion dans sa forme la plus simple.