Voir la source de Combinatoire

{{voir homonymes|combinatoire (homonymie)}}
[[Image:Encyclopedie volume 1-262.png|250px|vignette|Une planche de l'[[Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers|''Encyclopédie'']] de [[Diderot]] et d'[[Alembert]] illustrant l'article « Carreleur ».]]
En [[mathématiques]], la '''combinatoire''', appelée aussi '''analyse combinatoire''', étudie les configurations de collections finies d'objets ou les [[Combinaison sans répétition|combinaisons]] d'[[Ensemble fini|ensembles finis]], ainsi que les [[Dénombrement|dénombrements]].

== Généralités et historique ==
La combinatoire est présente dans toute l'antiquité en Inde et en Chine. [[Donald Knuth]], dans le volume 4A « Combinatorial Algorithms » de ''[[The Art of Computer Programming]]''<ref>Part 1 section 7.2.1.7. History and further references</ref>{{,}}<ref>Voir aussi {{chapitre
|titre ouvrage =Combinatorics: Ancient & Modern
|auteurs ouvrage =Robin Wilson et John J. Watkins (éditeurs)
|préface=Ronald Graham
|titre = Two thousand years of combinatorics
|éditeur = Oxford University Press
|date=2013
|pages totales = 392
|isbn=9780199656592
|auteur  = Donald Knuth|passage=3-37}}.</ref> parle de la génération de [[n-uplet]]s ; il dit que la génération de motifs combinatoires {{citation|a commencé alors que la civilisation elle-même prenait forme<ref>Texte original : ''« began as civilization itself was taking shape.''</ref>}} La présence de listes de n-uplets binaires peut être retracée durant des milliers d’années jusqu’en Chine, Inde et Grèce ; on en trouve au {{IIIe|millénaire}}.

Un résultat de combinatoire plus sophistiqué, remontant à l'[[Antiquité]] grecque<ref>{{ouvrage|langue=en|auteur=D. E. Knuth|titre=The Art of Computer Programming|volume= 4|chap=Fascicule 4, ''Generating All Trees; History of Combinationatorial Generation|année=2006|pages= vi+120 |ISBN=0-321-33570-8}}.</ref>, est attesté par l'anecdote suivante : [[Plutarque]] rapporte, dans les ''Propos de table'', une assertion de [[Chrysippe de Soles|Chrysippe]] {{Citation|contredite par tous les mathématiciens, et entre autres par [[Hipparque (astronome)|Hipparque]]<ref>{{ouvrage|auteur=Plutarque|trad=Ricard|titre=Le Banquet des Sophistes|éditeur=Lefèvre et Charpentier|lieu=Paris|année=1844|lire en ligne= http://remacle.org/bloodwolf/historiens/Plutarque/stoiciens.htm |chap= Des contradictions des Stoïciens|passage=84}}.</ref>}}, sur le nombre de façons de combiner dix propositions. Hipparque savait que le nombre de « propositions composées positives » que l'on peut former à partir de dix propositions simples est {{unité|103049}}, et que le nombre de propositions négatives est {{formatnum:310952}}. Cette affirmation est restée inexpliquée jusqu'en 1994, quand David Hough, un étudiant de l'[[université George-Washington]], observe qu'il y a {{formatnum:103049}} façons de parenthéser une suite de dix éléments<ref>{{article|auteur1=J.-J. Dupas |auteur2=J.-A. Roddier|titre=Les racines grecques de l'analyse combinatoire|périodique=Tangente|numéro= Hors-série 39|année=2010|passage=6}}.</ref>{{,}}<ref name="stan-ec">{{Enumerative Combinatorics|vol=1}}.</ref>{{,}}<ref name="stan-amm">{{article|lang=en
 | nom = Stanley | prénom = Richard P. | lien auteur = Richard P. Stanley
 | doi = 10.2307/2974582
 | numéro = 4
 | journal = [[The American Mathematical Monthly|Amer. Math. Monthly]]
 | mr = 1450667
 | pages = 344-350
 | titre = Hipparchus, Plutarch, Schröder, and Hough
 | url = http://www-math.mit.edu/~rstan/papers/hip.pdf
 | volume = 104
 | année = 1997}}.</ref>{{,}}<ref name="acerbi">{{article|lang=en
 | nom = Acerbi | prénom = F.
 | journal =[[Archive for History of Exact Sciences|Arch. Hist. Exact Sci.]]
 | pages = 465-502
 | titre = On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics
 | url = http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub5.pdf
 | volume = 57
 | année = 2003}}.</ref>. Une explication semblable peut être donnée pour le deuxième nombre : il est très proche de {{nobr|1=({{formatnum:103049}} + {{formatnum:518859}})/2 = {{formatnum:310954}}}}, qui est la moyenne des dixième et onzième [[nombre de Schröder-Hipparque|nombres de Schröder-Hipparque]], et qui compte le nombre de parenthésages de dix termes avec un signe<ref name="acerbi"/>.

Parmi les autres précurseurs, on peut citer le mathématicien indien du {{s-|VI}} [[Varahamihira#Contributions_aux_sciences|Varāhamihira]]<ref name="varamihira">{{Article|langue=anglais|auteur1=Takao Hayashi|titre=Varāhamihira's pandiagonal magic square of the order four|périodique=Historia Mathematica|date=1987|issn=|lire en ligne=https://www.sciencedirect.com/science/article/pii/031508608790019X|pages=159 - 166, vol 14, issue 2.}}</ref> (''k'' parmi ''n'' avec exemple de 4 parmi 16), [[Bhāskara II]]<ref>B. Hauchecorne, « De la théologie à la combinatoire moderne », ''[[Tangente (magazine)|Tangente]]'', Hors série {{n°|39}}, {{p.|8-9}}.</ref> au {{s-|XII}} (nombre de choix de ''p'' éléments parmi ''n'').

Parmi les mathématiciens de langue arabe, on peut citer  [[Ahmad Ibn Mun'im]], mathématicien [[maroc]]ain de la fin du {{sp|XII|e|et du début du|XIII|e}}<ref>
Ibn Mun'im traite de la combinatoire comme un chapitre des mathématiques dans son livre ''Fiqh Al Hisab'' {{Lien web|langue=francais|titre=biologie antique et Moyen Âge|url=http://www.epsnv-alger.dz/wp-content/uploads/biologie-antique-et-moyen-age-suite-1.pdf|site=epsnv-alger.dz|date=|consulté le=12 fevrier 2018}}
</ref>{{,}}<ref>
{{Ouvrage|langue=fr|prénom1=Ahmed|nom1=Djebbar|titre=L'Âge d'or des sciences arabes|éditeur=Humensis|date=2017-03-14|pages totales=192|isbn=978-2-7465-1220-7|lire en ligne=https://books.google.fr/books?id=mTaWDgAAQBAJ&pg=PT23&dq=ibn+mun%27im+combinatoire|consulté le=2018-02-18}}.</ref>{{,}}<ref>{{chapitre
|titre ouvrage =Combinatorics: Ancient & Modern
|auteurs ouvrage =Robin Wilson et John J. Watkins (éditeurs)
|préface=Ronald Graham
|titre = Islamic combinatorics
|éditeur = Oxford University Press
|date=2013
|pages totales = 392
|isbn=9780199656592
|auteur  = Ahmed Djebbar|passage=83-107}}.</ref> et le mathématicien de [[Marrakech]], [[Ibn al-Banna' al-Marrakushi|Ibn Al-Banna]], qui  propose une approche arithmétique  en  établissant une relation explicite entre les expressions combinatoires et les sommes de suites finies d'entiers ou les éléments du tableau des [[nombre figuré|nombres figurés]] (trigone, décagone, etc..)<ref>{{Chapitre|langue=en|auteur1="Ahmed Djebbar"|titre chapitre="Islamic combinatorics"|auteurs ouvrage="Robin Wilson et John J. Watkins"|titre ouvrage="Combinatorics : Ancient and modern"|lieu="Oxford"|éditeur="Oxford University Press"|année=2013|pages totales="381 p."|passage="p.99 à 101"|isbn=978-0-19-965659-2}}</ref>.

En Europe, on compte les apports de [[Raymond Lulle]] au {{s-|XIII}}, [[Gersonide]] au début du {{s-|XIV}} (rapport entre le nombre d'arrangements et le nombre de combinaisons), [[Michael Stifel]] au {{s-|XVI}} (première approche du [[triangle de Pascal]]). Elle se développe de façon significative à partir du {{XVIIe siècle}}, en même temps que le calcul des [[probabilités]], avec [[Blaise Pascal]] et [[Pierre de Fermat]]. Initialement, elle avait pour objet la résolution des problèmes de dénombrement, provenant de l'étude des jeux de hasard. Plus tard, elle se lia à la [[théorie des nombres]] et à la [[théorie des graphes]].

En particulier, la combinatoire s'intéresse aux méthodes permettant de compter les éléments dans des ensembles finis (combinatoire énumérative) et à la recherche des optima dans les configurations ainsi qu'à leur existence ([[combinatoire extrémale]]).

Voici quelques exemples de situations donnant lieu à des questions d'analyse combinatoire :
* les rangements de livres sur une étagère ;
* les dispositions de personnes autour d'une table ronde ;
* les tirages avec remise d'un certain nombre de boules numérotées dans une urne ;
* les placements de jetons sur un damier ;
* le nombre d'ordonnancements possibles des cartes d'un jeu de 52 cartes.<br />Dans ce dernier exemple, le nombre est égal à 52! (le « ! » dénotant la [[factorielle]]). Il peut sembler étonnant que ce nombre, environ {{formatnum:8.065817517094}}&nbsp;{{x10|67}}, soit si grand. C'est environ 8 suivi de 67 zéros. Il est, par exemple, beaucoup plus grand que le [[nombre d'Avogadro]], égal à 6,022&nbsp;{{x10|23}}.

== Domaines de la combinatoire ==

=== Combinatoire énumérative ===
[[Image:Catalan 4 leaves binary tree example.svg|upright=2|droite|vignette|Cinq [[Arbre binaire|arbres binaires]] à trois [[théorie des graphes|sommets]], un exemple de [[nombre de Catalan]].]]
{{article détaillé|Dénombrement}}

La combinatoire énumérative est le domaine le plus classique de la combinatoire, et s'intéresse au dénombrement de certains objets combinatoires. Même si le dénombrement des éléments d'un ensemble est un problème mathématique plutôt vaste, de nombreux problèmes qui se présentent dans diverses applications ont des descriptions combinatoires plutôt simples. La suite des [[Suite de Fibonacci|nombres de Fibonacci]] est un exemple de base d'un problème de combinatoire énumérative. Il existe un modèle appelé en anglais ''{{Lien|langue=en|trad=Twelvefold way|fr=Twelvefold way}}'' qui constitue un cadre unifié pour les problèmes de dénombrement des [[permutation]]s, [[Combinaison (mathématiques)|combinaisons]] et [[Partition d'un ensemble|partitions]].

La combinatoire moderne comporte de nombreux champs très développés, et utilise des outils puissants empruntés à des branches mathématiques parfois inattendues ; on distingue ainsi :

=== Théorie combinatoire des nombres ===
{{Article détaillé|contenu=Article détaillé : {{lien|trad=arithmetic combinatorics|combinatoire arithmétique}}}}
La ''théorie combinatoire des nombres''  (ou ''combinatoire arithmétique'') s'occupe des problèmes de [[théorie des nombres]] qui impliquent les idées combinatoires dans leurs formulations ou leurs solutions. [[Paul Erdős]] est le principal fondateur de cette branche de la théorie des nombres. Les sujets caractéristiques incluent les [[Système couvrant|systèmes couvrants]], les [[Jeu à somme nulle|jeux à somme nulle]], diverses sommes d'ensembles restreintes et des [[Suite arithmétique|progressions arithmétiques]] dans l'ensemble des entiers. Les méthodes algébriques ou analytiques sont puissantes dans ce champ d'étude.

=== Combinatoire des mots ===
[[Image:Morse-Thue sequence.gif|vignette|droite|Construction de la [[suite de Prouhet-Thue-Morse]].]]
{{article détaillé|Combinatoire des mots}}
La ''combinatoire des mots'' applique la combinatoire aux [[mot (mathématiques)|mots]] finis ou infinis. Cette branche s'est développée à partir de plusieurs branches des mathématiques : la [[théorie des nombres]], la [[théorie des groupes]], les [[Probabilité|probabilités]] et bien sûr la combinatoire. Elle a des liens avec divers thèmes informatiques, comme la [[Algorithme de recherche de sous-chaîne|recherche de motifs]] dans un texte ou la [[compression de données|compression]] de textes.

=== Combinatoire algébrique ===
{{article détaillé|Combinatoire algébrique}}
La ''combinatoire algébrique'' est une discipline qui traite de l'étude des [[structure algébrique|structures algébriques]] par des techniques [[algorithme|algorithmiques]] et combinatoires,
comme notamment illustré par les travaux de [[Marcel-Paul Schützenberger]], [[Alain Lascoux]], [[Dominique Foata]] et [[Richard Peter Stanley|Richard Stanley]]. L'intérêt de la [[combinatoire algébrique]] vient du fait que la plupart des structures en algèbre abstraite sont soit finies, soit engendrées par un ensemble fini d'éléments, ce qui rend possible leur manipulation de manière algorithmique.

=== Combinatoire analytique ===
{{article détaillé|Combinatoire analytique}}
La ''combinatoire analytique'' (en {{lang-en|analytic combinatorics}}) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des [[série génératrice|séries génératrices]], et s'appuyant en particulier sur l'[[analyse complexe]] pour obtenir des résultats [[comportement asymptotique|asymptotiques]] sur les objets combinatoires initiaux. Les résultats de [[combinatoire analytique]] permettent notamment une analyse fine de la [[analyse de la complexité des algorithmes|complexité]] de certains [[algorithme]]s.

=== Combinatoire probabiliste ===
{{article détaillé|Méthode probabiliste}}
[[Fichier:Self avoiding walk.svg|vignette|Chemin sans contact dans une grille.]]
La ''combinatoire probabiliste'' ou ''méthode probabiliste'' est une méthode [[Démonstration constructive|non constructive]], initialement utilisée en combinatoire et lancée par [[Paul Erdős]], pour démontrer l'existence d'un type donné d'objet [[mathématique]]. Cette méthode a été appliquée à d'autres domaines des mathématiques tels que la [[théorie des nombres]], l'[[algèbre linéaire]] et l'[[analyse réelle]]. Son principe est de montrer que si l'on choisit au hasard des objets d'une catégorie, la [[probabilité]] que le résultat soit d'un certain type est plus que zéro. Bien que la démonstration utilise la [[théorie des probabilités]], la conclusion finale est déterminée ''de façon certaine''.

=== Combinatoire topologique ===
{{Article détaillé|contenu=Article détaillé : [[Combinatoire topologique]]}}
[[Image:Collier-de-perles-rouge-vert.svg|vignette|droite|[[problème du partage d'un collier|Partage d'un collier]] en deux coupes.]]
En combinatoire topologique, on utilise des concepts et méthodes de la [[topologie]] dans l'étude de problèmes comme la [[coloration de graphe]], le [[partage équitable]], la [[partition d'un ensemble]], les [[poset]]s (ensembles partiellement ordonnés), les [[Arbre de décision|arbres de décision]], le [[problème du partage d'un collier]] ou la {{Lien|langue=en|trad=Discrete Morse theory|fr=théorie de Morse discrète}}. Ne pas confondre avec la [[topologie combinatoire]] qui est une ancienne dénomination pour [[topologie algébrique]].

=== Combinatoire géométrique ===
[[Fichier:Icosahedron.svg|vignette|[[Icosaèdre]].]]
{{Article détaillé|contenu=Article détaillé : [[Combinatoire géométrique]]}}
La ''combinatoire géométrique'' inclut un certain nombre de thèmes comme la combinatoire des polyèdres (étude des [[Face (géométrie)|faces]] de polyèdres convexes), la géométrie convexe (étude des [[Ensemble convexe|ensembles convexes]], en particulier la combinatoire de leurs intersections), et la [[géométrie discrète]], qui à son tour a de nombreuses applications en [[géométrie algorithmique]]. D'autres domaines important sont la [[Espace métrique|géométrie métrique]] des [[polyèdre]]s, tels que le [[théorème de Cauchy (géométrie)|théorème de Cauchy]] sur la rigidité des polytopes convexes. L'étude des [[Polytope régulier|polytopes réguliers]], des [[Solide d'Archimède|solides d'Archimède]], ou des [[Kissing number|kissing numbers]] font également partie de la combinatoire géométrique. Des polytopes particuliers sont aussi considérés, comme le [[permutoèdre]], l'[[associaèdre]] et le {{Lien|langue=en|trad=Birkhoff polytope|fr=polytope de Birkhoff}} (sur les [[Matrice bistochastique|matrices bistochastiques]]).

=== Combinatoire extrémale et Théorie de Ramsey ===
{{article détaillé|Théorie de Ramsey}}
La ''théorie de Ramsey'', portant le nom de [[Frank Ramsey]], tente typiquement de répondre à des questions de la forme : « combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? » Un exemple type est le [[théorème de Ramsey]] qui affirme que, pour tout entier <math>n</math>, tout [[graphe complet]] suffisamment grand dont les [[graphe (mathématiques discrètes)|arêtes]] sont colorées contient des sous-graphes complets de taille <math>n</math> d'une seule couleur.

== Domaines connexes ==
De plus, on rencontre des outils combinatoires dans les domaines suivants :

=== Théorie des graphes ===
[[Fichier:Petersen1 tiny.svg|vignette|[[Graphe de Petersen]].]]
{{article détaillé|Théorie des graphes}}
La ''théorie des graphes'' est une théorie [[informatique]] et [[mathématique]]. Les [[Liste des algorithmes de la théorie des graphes|algorithmes élaborés]] pour résoudre des problèmes concernant les [[Lexique de la théorie des graphes|objets de cette théorie]] ont de nombreuses applications dans tous les domaines liés à la notion de réseau et dans bien d'autres domaines, tant le concept de graphe est général. De grands théorèmes difficiles, comme le [[théorème des quatre couleurs]], le [[théorème des graphes parfaits]], ou encore le [[théorème de Robertson-Seymour]], ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la [[conjecture d'Hadwiger]], en font une branche vivace des [[mathématiques discrètes]].

=== Théorie des partitions ===
[[Fichier:Ferrer partitioning diagrams.svg|vignette|droite|[[Diagramme de Ferrers|Diagrammes de Ferrers]] des partitions des entiers jusqu'à 8.]]
{{article détaillé|Partition d'un entier}}
La théorie des partitions étudie divers problèmes d'énumération et de comportement asymptotique liés aux
[[Partition d'un entier|partitions d'un entier]], et a des relations étroites avec les [[q-analogue]]s, les [[Fonction spéciale|fonctions spéciales]] et les [[polynômes orthogonaux]]. Au départ, elle fait partie de la [[théorie des nombres]] et de l'[[analyse (mathématiques)|analyse]]. Elle est considérée maintenant comme une partie de la combinatoire, ou comme un domaine indépendant. Elle utilise l'approche par [[preuve bijective|preuve par bijection]] et emploie divers outils d'analyse, de [[théorie analytique des nombres]], et a des connexions avec la [[physique statistique]].

=== Théorie des matroïdes ===
{{article détaillé|Matroïde}}
Un ''matroïde'' est un objet mathématiques introduit en 1935 par [[Hassler Whitney|Whitney]], qui a pour vocation initiale de saisir l'essence du concept d'[[indépendance linéaire]]. Elle est donc naturellement liée à l'[[algèbre linéaire]] et aussi à la [[théorie des graphes]] et à la [[géométrie]].

=== Théorie des ordres ===
[[Fichier:Hypercubeorder binary.svg|vignette|[[Hypercube (graphe)|Hypercube]].]]
{{article détaillé|Relation d'ordre}}
Un '''poset''' (de l'anglais ''partially ordered set'', en français "ensemble partiellement ordonné") formalise et généralise la notion intuitive d'ordre ou d'arrangement entre les éléments d'un [[ensemble]]. Un poset est un ensemble muni d'une [[relation d'ordre]] qui indique que pour certains couples d'éléments, l'un est plus petit que l'autre. Tous les éléments ne sont pas forcément comparables, contrairement au cas d'un ensemble muni d'un [[ordre total]]. Si l'ensemble est fini, on dispose d'une représentation graphique du poset, qui est [[diagramme de Hasse]].

=== Plans en blocs ===
{{article détaillé|design combinatoire|plan en blocs}}
Un '''[[plan en blocs]]''' (en anglais {{Citation étrangère|langue=en|block design}}) est un cas particulier des '''systèmes de blocs''' : il est formé d'un ensemble muni d'une famille de sous-ensembles (distincts ou non selon les cas). Ces sous-ensembles sont choisis de manière à satisfaire certaines propriétés correspondant à une application particulière. Les applications viennent de domaines varies, y compris les [[plan d'expérience|plans d'expérience]], [[géométrie finie]], [[test (informatique)|test de logiciel]], [[cryptographie]], et [[géométrie algébrique]]. De nombreuses variantes ont été étudiées, les plus considérés sont les ''plans en blocs incomplets équilibrés''.

=== Séries génératrices ===
{{article détaillé|Série génératrice}}
Une ''série génératrice'' est une [[série formelle]] dont les [[coefficient]]s codent une [[suite (mathématiques)|suite]] de nombres (ou plus généralement de [[polynôme]]s, etc.). Il existe plusieurs sortes de séries génératrices, comme les ''séries génératrices exponentielles'', les ''[[Série de Lambert|séries de Lambert]]'', les ''[[Série de Dirichlet|séries de Dirichlet]]'', etc. On peut associer à toute suite une série génératrice de chaque type, mais la facilité de manipulation de la série dépend considérablement de la nature de la suite associée, et du problème qu'on cherche à étudier. L'intérêt des séries est qu'il est souvent possible d'étudier une suite donnée à l'aide de manipulations formelles de la série génératrice associée, ainsi qu'en utilisant les [[analyse (mathématiques)|propriétés analytiques]] de la fonction somme de la série.

== Permutations (dispositions, ordonnancements) ==

Les deux sections qui suivent sont une présentation détaillée et élémentaire de quelques notions et théorèmes de base.
=== Permutations sans répétition d'objets discernables ===
{{Article détaillé|Permutation}}

Les permutations sans répétition d'un ensemble fini <math>E</math> sont les [[bijection]]s de <math>E</math> sur lui-même.

Comme exemple d'introduction, considérons le nombre de dispositions de six objets discernables dans six cases consécutives numérotées avec un et un seul objet par case. Chacun des objets peut être placé dans la première case, ce qui donne six possibilités d'occuper la première place. Une fois la première place occupée par l'un des objets, il reste encore cinq candidats pour la deuxième place, la deuxième place étant attribuée, il reste seulement quatre candidats pour la troisième place, et ainsi de suite. Pour l'avant-dernière place, il ne reste plus que deux objets, et une fois l'un des deux placé, la dernière place doit être occupée par le dernier objet.

Il y a ainsi <math>6\times 5\times 4\times 3\times 2\times 1</math> ou <math>6!=720</math> possibilités de disposer six objets discernables.

;Généralisation :

Nous allons voir que le nombre de dispositions de <math>n</math> éléments discernables est égal à <math>n!</math>

Une disposition des objets d'un ensemble <math>E</math> de cardinal <math>n</math>, dans <math>n</math> cases avec un et un seul objet par case, ou un ordonnancement des éléments de <math>E</math> se représente par une bijection de <math>\{1, 2, \ldots, n\}</math> dans <math>E</math> ou une permutation de <math>E</math>. Il est commode de représenter une telle bijection par un [[n-uplet|''n''-uplet]] (ou ''n''-liste) d'éléments de 
<math>E,(x_1,x_2,\ldots,x_n)</math>

{{théorème|Il y a <math>n!</math> permutations (sans répétition) de <math>n</math> éléments.}}

En effet, pour former un [[n-uplet|''n''-uplet]] d'éléments de ''E'', nous devons choisir un élément de ''E'' pour la première place du [[n-uplet|''n''-uplet]] et il y a ''n'' possibilités, il y a ''n'' - 1 choix possibles d'un élément de ''E'' pour la deuxième place, ''n'' - 2 pour la troisième, etc. Il n'y a plus qu'un seul choix d'élément pour la dernière place. Donc au total ''n'' × (''n''-1) × (''n''-2) × … × 2 × 1 permutations.

Cette propriété se [[Raisonnement par récurrence|démontre par récurrence]] sur ''n''.

=== Permutations avec répétition d'objets discernables ===
{{Article détaillé|Permutation avec répétition}}
Pour déterminer le nombre des dispositions possibles d'objets de plusieurs classes et mutuellement indiscernables dans chaque classe, il est utile de considérer le nombre de dispositions possibles de ces objets en les supposant tous discernables, et ensuite de trouver combien de ces dispositions sont indiscernables. Le nombre des dispositions possibles de ces objets est égal au nombre de dispositions possibles des objets considérés comme discernables divisé par le nombre des dispositions indiscernables.

Par exemple, si nous devons déterminer le nombre total de dispositions d'objets dont deux sont d'une première classe, trois d'une deuxième classe et cinq d'une troisième classe, alors nous calculons le nombre total de dispositions de ces objets considérés comme discernables, ce qui donne (2 + 3 + 5)!, soit {{formatnum:3628800}} dispositions possibles. Mais certaines dispositions restent inchangées lorsque les objets indiscernables d'une même classe sont échangés mutuellement, et il y a 2! × 3! × 5! soit {{formatnum:1440}} façons de permuter les objets de chacune de ces classes.

Nous obtenons au total {{formatnum:3628800}} ÷ {{formatnum:1440}} = {{formatnum:2520}} dispositions différentes. Il s'agit aussi du nombre de permutations avec répétition de 10 éléments avec 2, 3 et 5 répétitions.

;Généralisation :

{{théorème|Le nombre de permutations de ''n'' éléments, répartis dans ''k'' classes dont ''n''<sub>1</sub> sont de classe 1, ''n''<sub>2</sub> sont de classe 2, …, ''n''<sub>k</sub> sont de classe ''k'', indiscernables dans chaque classe, ou le nombre de permutations de ''n'' éléments avec ''n''<sub>1</sub>, ''n''<sub>2</sub>, …, ''n''<sub>k</sub> répétitions, avec <math>\left ( \sum^k_{i=1} n_i = n \right )</math>, est égal à : <math>\frac{n!}{n_1! n_2! \ldots n_k!}</math>.}}

== Arrangements (choix en tenant compte de l'ordre) ==
=== Arrangements sans répétition ===
{{Article détaillé|Arrangement}}
Nous disposons de ''n'' objets discernables et nous voulons en placer ''k'', en tenant compte de l'ordre, dans ''k'' cases numérotées de 1 à ''k'' avec un et un seul objet par case. Le nombre de dispositions est alors égal au nombre de ''k''-listes distinctes formées à partir de ces objets.
Au lieu de constituer un [[n-uplet|''n''-uplet]], à partir de ''n'' objets discernables, nous formons ici des [[n-uplet|''k''-uplets]] avec <!--''k''≤''n'', (''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''k''</sub>)--> <math>k \le n \text{,} \left( x_1, x_2, \ldots, x_k \right)</math> à partir de ces ''n'' objets tels que pour <math>i \neq j</math>, on ait <math>x_i \neq x_j</math>. Un tel [[n-uplet|''k''-uplet]] s'appelle un arrangement sans répétition de ''n'' éléments pris ''k'' à ''k''.

{{Théorème|Le nombre d'arrangements sans répétition de ''n'' éléments pris ''k'' à ''k'' est égal à <math>A_n^k</math> (égal à <math>\frac{n!}{(n-k)!}</math> si ''k''≤''n'' et à 0 sinon).}}

En effet, Il y a ''n'' choix possibles de l'objet qui occupe la première place du [[n-uplet|''k''-uplet]], ''n''-1 choix pour l'objet de la {{2e|place}} ; pour la ''k''{{e}}, il ne reste plus que ''n''-(''k''-1) objets et donc ''n''-''k''+1 choix possibles. Le produit <!--''n''(''n''-1)…(''n''-''k''+1)--> <math>n \cdot (n-1) \ldots (n-k+1)</math> s'écrit bien sous la forme : <math>\frac{n!}{(n-k)!}</math>. C'est juste le nombre des [[Injection (mathématiques)|injections]] de l'ensemble {1,2, ..., k} dans l'ensemble {1,2, ..., n}.

Le cas ''n'' = ''k'' nous oblige alors à diviser par (0)! (rappelons que (0)! vaut 1).

=== Arrangements avec répétition ===
{{Article détaillé|Arrangement avec répétition}}
Lorsque nous voulons placer des objets pris parmi ''n'' objets discernables dans ''k'' emplacements en tenant compte de l'ordre, ces objets pouvant apparaître plusieurs fois, le nombre de dispositions est alors égal au nombre de [[n-uplet|''k''-uplets]] formés à partir de ces ''n'' objets.
Un tel [[n-uplet|''k''-uplet]], avec ''k''≤''n'', (''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''k''</sub>) formé à partir de ces ''n'' objets s'appelle un arrangement avec répétition de ''n'' éléments pris ''k'' à ''k''.

Comme chaque emplacement peut être occupé indifféremment par l'un quelconque de ces ''n'' objets, il y en a au total ''n''<sup>''k''</sup>.

Quand nous tirons 11 fois l'un de 3 numéros en tenant compte de l'ordre d'apparition nous obtenons au total 3{{exp|11}} = {{formatnum:177147}} tirages différents. Comme exemple tiré de la génétique, nous pouvons donner le nombre total de [[codon]]s de base (triplets formés de quatre codes) : 4{{exp|3}}= 64.

== Combinaisons (choix sans tenir compte de l'ordre) ==
Contrairement aux arrangements, les combinaisons sont des dispositions d'objets qui ne tiennent pas compte de l'ordre de placement de ces objets. Par exemple, si ''a'', ''b'' et ''c'' sont des boules tirées d'une urne, ''abc'' et ''acb'' correspondent au même tirage. Il y a donc moins de combinaisons que d'arrangements.

=== Combinaisons sans répétition ===
{{Article détaillé|Combinaison (mathématiques)}}
Si nous tirons sans remise ''k'' objets parmi ''n'' objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition, nous pouvons représenter ces ''k'' objets par une partie à ''k'' éléments d'un ensemble à ''n'' éléments. Ce sont des combinaisons sans répétition de ''n'' éléments pris ''k'' à ''k''.

Pour déterminer le nombre de ces dispositions, nous pouvons déterminer le nombre d'arrangements de ''k'' objets et diviser par le nombre de dispositions obtenues les unes à partir des autres par une permutation. Il y en a <math>{n \choose k}=\frac{A_n^k}{k!}=C_n^k</math> (pour la notation, voir aussi l'article sur le [[coefficient binomial]]).

Par exemple le jeu [[Euromillions]] demande de choisir 5 nombres différents entre 1 et 50 et 2 nombres entre 1 et 12, soit <math>{50 \choose 5} \times {12 \choose 2}=139\,838\,160</math> possibilités.

=== Combinaisons avec répétition ===
{{Article détaillé|Combinaison avec répétition}}
Si nous tirons avec remise ''k'' objets parmi ''n'' objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition, ces objets peuvent apparaître plusieurs fois et nous ne pouvons les représenter ni avec une partie à ''k'' éléments, ni avec un [[n-uplet|''k''-uplet]] puisque leur ordre de placement n'intervient pas. Il est cependant possible de représenter de telles dispositions avec des applications appelées combinaisons avec répétition.

{{théorème|Le nombre de combinaisons avec répétition de ''n'' éléments pris ''k'' à ''k'' est égal à : <math>\Gamma_n^k={ n+k-1 \choose k}</math>.}}

Donnons l'exemple du jeu de domino. Les pièces sont fabriquées en disposant côte à côte deux éléments de l'ensemble {blanc, 1, 2, 3, 4, 5, 6}. Si nous retournons un domino, nous changeons l'ordre des deux éléments, mais le domino reste identique. Nous avons une combinaison avec répétition de 7 éléments pris 2 à 2, et au total il y a : <math>\Gamma_7^2={8 \choose 2}=28</math> dominos dans un jeu.

== Fonction de comptage ==

Soit ''S''<sub>''n''</sub> l'ensemble des permutations de {1, 2, …, ''n''}. Nous pouvons considérer la fonction qui à ''n'' associe le nombre de permutations. Cette fonction est la fonction factorielle et sert à compter les permutations.

Étant donné une collection infinie d'ensembles finis <!--{''E''<sub>''n''</sub>/''n''∈ℕ}--> <math>\left\{ E_n | n \in \mathbb{N} \right\}</math> indexée par l'ensemble des [[Entier naturel|entiers naturels]], une fonction de comptage est une fonction qui à un entier ''n'' associe le nombre d'éléments de ''E''<sub>''n''</sub>. Une fonction de comptage ''f'' permet donc de compter les objets de ''E''<sub>''n''</sub> pour n'importe quel ''n''. Les éléments de ''E''<sub>''n''</sub> ont habituellement une description combinatoire relativement simple et une structure additionnelle, permettant souvent de déterminer ''f''.

Certaines fonctions de comptage, sont données par des formules « fermées », et peuvent être exprimées comme [[Composition de fonctions|composées]] de fonctions élémentaires telles que des factorielles, des puissances, et ainsi de suite.

Cette approche peut ne pas être entièrement satisfaisante (ou pratique) pour certains problèmes combinatoires. Par exemple, soit ''f''(''n'') le nombre de sous-ensembles distincts de nombres entiers dans l'intervalle [1, ''n''] qui ne contiennent pas deux nombres entiers consécutifs. Par exemple, avec ''n'' = 4, nous obtenons ∅, { 1 }, { 2 }, { 3 }, { 4 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, et donc f(4) = 8. Il s'avère que ''f''(''n'') est le ''n''ème [[nombre de Fibonacci]], qui peut être exprimé sous la forme « fermée » suivante :
:<math>f(n)=\frac{\phi^n}{\sqrt{5}}-\frac{(1-\phi)^n}{\sqrt{5}}</math>
où <math>\phi=\dfrac{1+\sqrt 5}{2}</math>, est le nombre d'or. Cependant, étant donné que nous considérons des ensembles de nombres entiers, la présence du <math>\sqrt 5</math> dans le résultat peut être considérée comme inesthétique d'un point de vue combinatoire. Aussi <math>f(n)</math> peut-il être exprimé par une relation de récurrence :
:<math>f(n)=f(n-1)+f(n-2)</math>
ce qui peut être plus satisfaisant (d'un point de vue purement combinatoire), puisque la relation montre plus clairement comment le résultat a été trouvé.

Dans certains cas, un équivalent asymptotique <math>g</math> de <math>f</math>,
:<math>f(n)\sim g(n)</math> quand <math>n</math> tend vers l'infini
où ''g'' est une fonction « familière », permet d'obtenir une bonne approximation de ''f''. Une fonction asymptotique simple peut être préférable à une formule « fermée » extrêmement compliquée et qui informe peu sur le comportement du nombre d'objets. Dans l'exemple ci-dessus, un équivalent asymptotique serait :
:<math>f(n)\sim\frac{\phi^n}{\sqrt{5}}</math>
quand ''n'' devient grand.

Une autre approche est celle des [[Série entière|séries entières]]. ''f''(''n'') peut être exprimé par une série entière formelle, appelée fonction génératrice de ''f'', qui peut être le plus couramment :
* la fonction génératrice ordinaire
:<math>\sum_{n > 0} f(n) \cdot x^n</math>
* ou la fonction génératrice exponentielle
:<math>\sum_{n > 0} f(n) \cdot \frac{x^n}{n!}</math>
Une fois déterminée, la fonction génératrice peut permettre d'obtenir toutes les informations fournies par les approches précédentes. En outre, les diverses opérations usuelles comme l'addition, la multiplication, la dérivation, etc., ont une signification combinatoire ; et ceci permet de prolonger des résultats d'un problème combinatoire afin de résoudre d'autres problèmes.

== Quelques résultats ==
Un théorème, dû à [[Frank Ramsey]], donne un résultat surprenant. À une soirée à laquelle se rendent au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement ou au moins trois qui sont étrangères les unes aux autres.

;Démonstration :
soit <math>P_1</math> une personne quelconque présente à la soirée. Sur les ''n-1'' autres, soit elle en connaît au plus deux, soit elle en connaît au moins trois. Supposons que l'on soit dans le second cas, et soient <math>P_2,\, P_3 \text{ et } P_4</math> trois personnes connues de <math>P_1</math>. Si deux d’entre elles se connaissent, mettons <math>P_2 \text{ et } P_3</math>, alors <math>P_1,\, P_2 \text{ et } P_3</math> se connaissent toutes trois. Sinon, <math>P_2,\, P_3 \text{ et } P_4</math> ne se connaissent pas du tout, et le résultat annoncé est encore juste. Dans l’autre cas de figure (<math>P_1</math> connaît au plus deux personnes du groupe), le même raisonnement, inversé, fonctionne avec les trois personnes que <math>P_1</math> ne connaît pas.

(C'est un cas particulier du [[Théorie de Ramsey|théorème de Ramsey]].)

L'idée de trouver un ordre dans des configurations aléatoires mène à la théorie de Ramsey. Essentiellement, cette théorie indique que n'importe quelle configuration suffisamment grande contiendra au moins un autre type de configuration.

== Notes et références ==
{{Références}}

== Voir aussi ==
{{Autres projets|wikiversity = Combinatoire}}

=== Bibliographie ===
* {{Enumerative Combinatorics|vol=1 et 2}}
* {{Ouvrage 
|prénom1=Nicholas A. |nom1=Loehr |titre=Bijective combinatorics |éditeur=Chapman Hall/CRC |année=2011 |pages totales=612 |isbn=978-1-4398-4884-5}}
* {{Ouvrage | prénom1=Claude | nom1=Berge | titre=Principes de combinatoire | éditeur=Dunod | lieu=Paris | année=1968 }} {{commentaire biblio|Traduction anglaise : {{Ouvrage | titre=Principles of Combinatorics | éditeur=Academic Press | année=1971 | isbn=978-0-12-410978-0}}}}
* {{Ouvrage | prénom1=Louis | nom1=Comtet | titre=Analyse combinatoire, Tomes I et II | éditeur=Presses universitaires de France | collection=Sup - Le Mathématicien | lieu=Paris | année=1970 | isbn=}}
* {{Ouvrage|prénom1=Louis|nom1=Comtet|lien auteur1=Louis Comtet|titre=Advanced Combinatorics|sous-titre=The Art of Finite and Infinite Expansions|éditeur=Reidel|lieu=Dordrecht|année=1974|pages totales=343|isbn=978-90-277-0441-2|lire en ligne=https://books.google.fr/books?id=C0HPgWhEssYC}}{{commentaire biblio|Traduit du français par J. W. Nienhuys. Réimpression par Springer Netherlands en 2010 {{ISBN|978-9048183418}} {{Présentation en ligne|lien=https://link.springer.com/book/10.1007/978-94-010-2196-8/page/1}}}}
*{{Ouvrage|auteur1=Robin Wilson|directeur1=oui|auteur2=John Watkins|directeur2=oui|titre=Combinatorics|sous-titre=ancient and modern|éditeur=Oxford University Press|année=2013|pages totales=381|isbn=978-0-19-965659-2|doi=10.1093/acprof:oso/9780199656592.001.0001|lire en ligne=https://books.google.com/books?id=hRmMp4D12PIC&printsec=frontcover}}
* {{Ouvrage
 |auteur1=Ira Gessel
 |auteur2=Gian-Carlo Rota
 |responsabilité2=éditeurs
 |titre=Classic Papers in Combinatorics
 |éditeur=Birkhäuser
 |collection=Modern Birkhäuser Classics
 |année=1987
 |pages totales=x + 492 p.
 |isbn=
 |présentation en ligne=https://www.springer.com/gp/book/9780817648411
}}.
* {{Ouvrage 
|prénom1=Ömer |nom1=Eğecioğlu 
|prénom2=Adriano Mario |nom2=Garsia 
|titre=Lessons in enumerative combinatorics 
|éditeur=Springer |
collection=Graduate texts in mathematics 
|numéro dans collection = 290
|pages totales = xvi + 479 p.
|date=2021 |isbn=978-3-030-71249-5 |zbl =  1478.05001}}

=== Articles connexes ===
* Domaines connexes :
** [[Optimisation combinatoire]]
** [[Théorie des codes]]
** [[Géométrie algorithmique]]
** [[Phylogénie]]
* [[Combinaison avec répétition]]
* [[Mathématiques discrètes]]
* [[Mot sans facteur carré]]
* [[Physique combinatoire]]
* [[Principe d'inclusion-exclusion]]
* [[Coefficient binomial]]

=== Lien externe ===
* {{en}} [http://cepa.newschool.edu/het/profiles/ramsey.htm L'histoire de la pensée économique] : à propos de Frank P. Ramsey.

{{Palette|Domaines des mathématiques|Informatique théorique}}
{{Portail|mathématiques|Informatique théorique}}

[[Catégorie:Combinatoire|*]]