Combinatoire

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait 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 parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»). 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 . Un résultat de combinatoire plus sophistiqué, remontant à l'Antiquité grecque, est attesté par l'anecdote suivante : Plutarque rapporte, dans les Propos de table, une assertion de Chrysippe , 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 , et que le nombre de propositions négatives est . 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 façons de parenthéser une suite de dix éléments. Une explication semblable peut être donnée pour le deuxième nombre : il est très proche de , qui est la moyenne des dixième et onzième nombres de Schröder-Hipparque, et qui compte le nombre de parenthésages de dix termes avec un signe. Parmi les autres précurseurs, on peut citer le mathématicien indien du Varāhamihira (k parmi n avec exemple de 4 parmi 16), Bhāskara II au (nombre de choix de p éléments parmi n), ainsi que Ahmad Ibn Mun'im, mathématicien marocain de la fin du , plus tard Raymond Lulle au , Gersonide au début du (rapport entre le nombre d'arrangements et le nombre de combinaisons), Michael Stifel au (première approche du triangle de Pascal).