Combinatoire

Combinatoire est une branche de mathématiques pures concernant l'étude des discret (et habituellement finis) objets. Elle est liée à de nombreux autres domaines de mathématiques , comme l'algèbre , la théorie des probabilités , théorie ergodique et la géométrie , ainsi que des sujets appliqués en informatique et la physique statistique. Aspects de la combinatoire comprennent "compter" les objets répondant à certains critères ( combinatoire énumérative), de décider si les critères peuvent être satisfaits, et la construction et l'analyse des objets répondant aux critères (comme dans modèles combinatoires et la théorie des matroïdes), trouver des «plus grands», ou des objets "plus petite" «optimales» ( combinatoire et extrêmes optimisation combinatoire), et de trouver algébriques structures ces objets peuvent avoir ( combinatoire algébrique).

Combinatoire est autant à résoudre que le renforcement de la théorie problème, mais il a développé de puissantes méthodes théoriques, en particulier depuis la fin du XXe siècle (voir la page Liste des sujets combinatoire pour les détails de la mise au point plus récente du sujet). Une des parties les plus anciennes et les plus accessibles de la combinatoire est la théorie des graphes, qui a également de nombreux liens naturels vers d'autres zones.

Il existe de nombreux modèles combinatoires et théorèmes liés à la structure de jeux combinatoires. Ces concentrent souvent sur un partition ou partition ordonnée d'un ensemble. Voir la Liste des sujets de partition pour une liste élargie de sujets connexes ou sur la Liste des sujets combinatoire pour une liste plus générale. Certains des résultats les plus notables sont mis en évidence ci-dessous.

Un exemple d'une question combinatoire simple est la suivante: Quel est le nombre d'ordres possibles d'un jeu de 52 cartes de jeu distinctes? La réponse est 52! (52 factorielle ), qui est égale à environ 8,0658 x 10 ^67.

Un autre exemple d'un problème plus difficile: Compte tenu d'un certain nombre n de personnes, est-il possible de les assigner à des ensembles de sorte que chaque personne est en au moins un jeu, chaque couple de personnes est dans exactement un jeu ensemble, tous les deux ensembles ont exactement une personne en commun, et aucun ensemble contient tout le monde, tout sauf une personne, ou exactement une seule personne? La réponse dépend de n. Voir « théorie de la conception "ci-dessous.

Combinatoire est fréquemment utilisé dans la science de l'ordinateur pour obtenir des estimations sur le nombre d'éléments de certains jeux. Un mathématicien qui étudie la combinatoire est souvent considéré comme un combinatorialist ou combinatorist.

Histoire de la combinatoire

Utilisations premières

L'apparition de la nombre de Fibonacci cinq dans la prosodie. Il ya une façon d'organiser un temps, deux à deux, trois pour trois, et cinq pour quatre battements.

Les premiers livres sur la combinatoire sont de l'Inde. Un Jainist texte, le Sutra Bhagabati, avait la première mention d'un problème de combinatoire; il a demandé combien de façons on pourrait prendre six goûts une, deux ou trois goûts à la fois. Le Sutra a été écrit autour Bhagabati 300 avant JC, et donc était le premier livre de mentionner la fonction de choix . Les prochaines idées de combinatoire provenaient Pingala, qui était intéressé à la prosodie. Plus précisément, il a voulu savoir combien de façons un mètre syllabe six pourrait être fabriqué à partir de notes courtes et longues. Il a écrit ce problème dans le sutra Chanda (également Chandahsutra) dans le deuxième siècle avant JC. En outre, il a aussi trouvé le nombre de mètres qui avaient notes n longues et de courtes notes k, ce qui est équivalent à trouver les coefficients du binôme.

Les idées de la Bhagabati ont été généralisées par le mathématicien indien Mahariva en 850 AD, et le travail de Pingala de prosodie a été élargi par Bhaskara et Hemacandra en 1100 AD. Bhaskara était la première personne connue à trouver la fonction de choix généralisée, bien que Brahmagupta peut avoir connu plus tôt. Hemacandra a demandé combien de mètres existaient d'une certaine longueur si une longue note a été considéré comme deux fois plus longtemps que une courte note, qui est équivalent à trouver les nombres de Fibonacci.

Un Hexagram

Alors que l'Inde était le premier pays à publier les résultats sur la combinatoire, il y avait découvertes par d'autres nations sur des sujets similaires. La première connexion connue à combinatoire vient du Papyrus Rhind, problème 79, pour la mise en œuvre d'une série géométrique. La prochaine étape est détenu par le I Ching . Le livre est sur ce que les différents hexagrammes signifient, et pour ce faire, ils avaient besoin de savoir combien il y avait hexagrammes possible. Comme chaque hexagramme est une permutation avec des répétitions de six lignes, où chaque ligne peut être l'un des deux Etats, solides ou en pointillés, la combinatoire donne le résultat que leur sont hexagrammes. Un moine peut aussi avoir compté le nombre de configurations à un jeu similaire à Aller vers 700 AD. Bien que la Chine avait relativement peu de progrès dans la combinatoire énumérative, ils résolu un problème de conception combinatoire, le carré magique , environ 100 AD.

En Grèce, Plutarque écrit que les Xénocrate découvert le nombre de différentes syllabes possibles dans la langue grecque. Ceci, cependant, est peu probable parce que ce est l'un des rares mentions de combinatoire en Grèce. Le nombre ils ont trouvé, semble également trop rond pour être plus qu'une conjecture. .

Les carrés magiques sont restés un intérêt de la Chine, et ils ont commencé à généraliser leur origine 3 × 3 carrés entre 900 et 1300 AD. Chine correspondait avec le Moyen-Orient sur ce problème dans le 13ème siècle. Le Moyen-Orient a également appris à propos de coefficients binomiaux de travail indienne, et a trouvé la connexion à l'expansion polynomiale.

Combinatoire de l'Ouest

Combinatoire est arrivé en Europe au 13ème siècle par deux mathématiciens, Leonardo Fibonacci et Jordanus Nemorarius. Fibonacci de Liber Abaci introduit beaucoup de l'Arabie et de l'Inde à l'Europe des idées, y compris celle des nombres de Fibonacci. Jordanus était la première personne à organiser le coefficient binomial de dans un triangle, comme il le faisait dans la proposition 70 de De Arithmetica. Cela a également été fait dans le Moyen-Orient en 1265, et la Chine vers 1300. Aujourd'hui, ce triangle est connu comme le triangle de Pascal.

La contribution de Pascal au triangle qui porte son nom vient de son travail sur des preuves formelles à ce sujet, en plus de sa connexion entre elle et la probabilité. Avec Leibniz et ses idées sur les partitions du 17ème siècle, ils sont considérés comme les fondateurs de la combinatoire modernes.

Pascal et Leibniz ont compris que l'algèbre et la combinatoire correspondaient (aka, développement du binôme était équivalente à la fonction de choix.) Cela a été élargi par De Moivre, qui a trouvé l'expansion d'un multinomial. De Moivre a également trouvé la formule pour dérangements en utilisant le principe de l'inclusion-exclusion, une méthode différente de Nikolaus Bernoulli, qui les avait trouvés précédemment. Il a réussi à se rapprocher de la coefficients binomiaux et factorielle. Enfin, il a trouvé une forme fermée pour les nombres de Fibonacci en inventant fonctions génératrices.

Au 18ème siècle, Euler a travaillé sur les problèmes de combinatoire. En plus de travailler sur plusieurs problèmes de probabilité qui pointent vers combinatoire, il a travaillé sur la Visite chevaliers, Carré gréco-latin, Nombre d'Euler, et autres. Il a également inventé la théorie des graphes en résolvant le Sept ponts de Königsberg problème, qui entraînent également la formation de topologie . Enfin, il a innové avec partitions de par l'utilisation de fonctions génératrices.

Combinatoire énumérative

Compter le nombre de façons que certains modèles peuvent être formés est le problème central de la combinatoire énumérative. Deux exemples de ce type de problème comptent combinaisons et permutations comptant (comme discuté dans la section précédente). Plus généralement, compte tenu d'une collection d'ensembles finis infini {S _i} indexés par les nombres naturels , combinatoire énumérative cherche à décrire une fonction de comptage qui compte le nombre d'objets par S _n pour tout n. Bien que comptant le nombre d'éléments dans un ensemble est un assez large problème mathématique, bon nombre des problèmes qui se posent dans les applications ont une description relativement simple combinatoire.

Les plus simples de ces fonctions sont formules fermées, qui peuvent être exprimées comme une composition de fonctions élémentaires telles que factorielles , les pouvoirs, et ainsi de suite. Par exemple, comme montré ci-dessous, le nombre des différents ordres possibles d'un jeu de n cartes est f (n) = n!. Souvent, aucune forme fermée est initialement disponible. Dans ces cas, nous avons fréquemment premier dérivons une relation de récurrence, puis résoudre la récurrence d'arriver à la forme fermée souhaitée.

Enfin, f (n) peut être exprimé par un séries formelles, appelé son fonction génératrice, ce qui est le plus souvent le navigateur fonction ordinaire de production

ou la fonction génératrice exponentielle

Souvent, une formule fermée compliqué donne peu d'indications sur le comportement de la fonction de comptage du nombre d'objets comptés grandit. Dans ces cas, une simple rapprochement asymptotique peut être préférable. Une fonction est une approximation asymptotique si comme l'infini . Dans ce cas, nous écrivons .

Une fois déterminé, la fonction génératrice peut permettre d'extraire toutes les informations données par les approches précédentes. En outre, les différentes opérations naturelles sur les fonctions génératrices telles que l'addition, la multiplication, la différenciation, etc., ont une signification combinatoire; Ceci permet de prolonger les résultats d'une problème combinatoire afin de résoudre les autres.

Permutations avec répétitions

Quand l'ordre est important, et un objet peut être choisie plus d'une fois, le nombre de permutations est

où n est le nombre d'objets à partir de laquelle vous pouvez choisir et R est le nombre d'être choisi.

Par exemple, si vous avez les lettres A, B, C et D et vous souhaitez découvrir le nombre de façons de les organiser en trois configurations de lettres ( trigrammes)

1. questions d'ordre (par exemple, AB est différent de BA, les deux sont inclus que les possibilités)
2. un objet peut être choisie plus d'une fois (AA possible)

vous trouverez qu'il ya ³ ou 4 64 façons. Ce est parce que pour la première tranche, vous pouvez choisir l'une des quatre valeurs, pour la deuxième fente, vous pouvez choisir l'un des quatre, et la fente finale, vous pouvez choisir l'une des quatre lettres. Les multipliant ensemble donne le total.

Permutations sans répétitions

Lorsque les questions d'ordre et chaque objet peut être sélectionné seulement une fois, puis le nombre de permutations est

où n est le nombre d'objets à partir de laquelle vous pouvez choisir, r est le nombre à être choisi et "!" est le symbole standard signifie factorielle .

Par exemple, si vous avez cinq personnes et allez choisir trois des ceux-ci, vous aurez 5 / (5-3)! = 60 permutations.

Notez que si n = r (qui signifie le nombre d'éléments choisis est égal au nombre d'éléments à choisir, cinq personnes et ramasser tous les cinq), la formule devient

où 0! = 1.

Par exemple, si vous avez les mêmes cinq personnes et que vous voulez savoir combien de façons que vous pouvez les organiser, il serait 5! ou 5 × 4 × 3 × 2 × 1 = 120 façons. La raison pour cela est que vous pouvez choisir parmi 5 pour l'emplacement initial, alors vous êtes de gauche avec seulement 4 à choisir pour la deuxième fente, etc. les multipliant ensemble donne le total de 120.

Combinaisons sans répétitions

Lorsque l'ordre n'a pas d'importance et chaque objet peut être choisi qu'une seule fois, le nombre de combinaisons est le coefficient binomial :

où n est le nombre d'objets à partir de laquelle vous pouvez choisir et K est le nombre d'être choisi.

Par exemple, si vous avez dix chiffres et souhaitez choisir 5 vous auriez 10 / (5 (10 -! 5))! = 252 façons de choisir. Le coefficient binomial est aussi utilisé pour calculer le nombre de permutations à une loterie.

Combinaisons avec répétitions

Lorsque l'ordre n'a pas d'importance et un objet peut être choisie plus d'une fois, le nombre de combinaisons est

où n est le nombre d'objets à partir de laquelle vous pouvez choisir et K est le nombre d'être choisi.

Par exemple, si vous avez dix types de beignets (n) sur un menu à choisir et vous voulez trois beignets (k) il ya (10 + 3-1)! / 3 (10 - 1)! = 220 façons de choisir (voir aussi multiset).

Nombres de Fibonacci

Soit f (n) le nombre de sous-ensembles distincts de l'ensemble qui ne contiennent pas deux entiers consécutifs. Lorsque n = 4, on a les ensembles {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, de sorte que f (4 ) = 8. Nous comptons les sous-ensembles souhaités de en comptant séparément ces sous-ensembles qui contiennent élément et ceux qui ne le font pas. Si un sous-ensemble contient , Alors elle ne contient pas d'élément . Donc, il ya exactement des sous-ensembles qui contiennent élément souhaités . Le nombre de sous-ensembles qui ne contiennent pas est tout simplement . L'ajout de ces chiffres ensemble, nous obtenons la relation de récurrence:

où et .

Dès 1202, Leonardo Fibonacci étudié ces chiffres. Ils sont maintenant appelés nombres de Fibonacci ; en particulier, qui est connu comme le e nombre de Fibonacci. Bien que la relation de récurrence permet de calculer chaque nombre de Fibonacci, le calcul est inefficace. Toutefois, en utilisant des techniques classiques pour résoudre relations récurrence, nous pouvons atteindre le fermée solution de formulaire:

où , Le nombre d'or .

Dans l'exemple ci-dessus, une approximation asymptotique à est:

lorsque n devient grand.

Combinatoire structurels

Théorie des graphes

Les graphiques sont des objets de base de la combinatoire. Les questions vont de comptage (par exemple le nombre de graphes sur n sommets avec des bords k) à la structure (par exemple, qui contiennent des graphiques Cycles hamiltoniens).

théorie de la conception

Un résultat simple dans le bloc la zone de designs de la combinatoire est que le problème des ensembles formant, décrit dans l'introduction, a une solution seulement si n est de la forme q ² + q + 1. Il est moins simple de prouver qu'il existe une solution si q est un alimentation principale. On suppose que ce sont les seules solutions. Il a été en outre montré que, si une solution ne existe pour q congru à 1 ou 2 mod 4, alors q est égal à une somme de deux nombres carrés. Ce dernier résultat, le Bruck-Ryser théorème, est prouvé par une combinaison de méthodes constructives sur la base un corps fini et une application de formes quadratiques.

Quand il existe une telle structure, il est appelé un fini plan projectif; montrant ainsi comment géométrie et combinatoire finie croisent.

Théorie Matroid

Théorie Matroid abstraction partie de la géométrie . Il étudie les propriétés des ensembles (généralement, ensembles finis) de vecteurs dans un espace vectoriel qui ne dépendent pas sur les coefficients particuliers dans un relation de dépendance linéaire. Non seulement la structure, mais également des propriétés énumératives appartiennent à matroïde théorie.

Par exemple, étant donné un ensemble de n vecteurs dans l'espace euclidien , ce est le plus grand nombre d' avions qu'ils peuvent générer? Réponse: le coefficient binomial

Y at-il un ensemble qui génère exactement un plan sensiblement? (Non, dans presque tous les cas.) Ce sont des questions extrêmes en géométrie, comme on le verra ci-dessous.

Extremal et la combinatoire probabilistes

Beaucoup de questions extrêmes face à systèmes fixes. Un exemple simple est la suivante: quel est le plus grand nombre de sous-ensembles d'un n -Element mis l'on peut avoir, si aucun des deux sous-ensembles sont disjoints? Réponse: la moitié du nombre total de sous-ensembles. Preuve: Appelez le n -Element ensemble S. Entre tout sous-ensemble T et son compléter S - T, au plus on peut être choisie. Cela prouve le nombre maximum de sous-ensembles choisis ne est pas supérieure à la moitié du nombre de sous-ensembles. Pour montrer l'on peut atteindre la moitié du nombre, choisir un élément x de S et choisir tous les sous-ensembles qui contiennent x.

Un problème plus difficile est de caractériser les solutions extrêmes; dans ce cas, de montrer que pas d'autre choix de sous-ensembles peut atteindre le nombre maximal tout en satisfaisant l'exigence.

Souvent, ce est trop dur, même pour trouver le f extrémal de réponse (n) exactement et on ne peut donner une estimation asymptotique.

Théorie Ramsey

Théorie Ramsey est une partie célèbre de la combinatoire extrémaux. Il stipule que toute suffisamment grande configuration aléatoire contiendra un peu d'ordre.

Frank Ramsey se est avéré que pour tout entier k il existe un entier n tel que tout graphe à n sommets soit contient une clique ou un ensemble indépendant de taille k. Ce est un cas particulier de Théorème de Ramsey. Par exemple, compte tenu de tout groupe de six personnes, ce est toujours le cas que l'on peut trouver trois personnes sur ce groupe soit se connaissent tous ou ne savez pas à l'autre. La clé de la preuve dans ce cas est le Pigeonhole Principe: soit A connaît trois des personnes qui restent, ou A ne sait pas trois des personnes restantes.

Voici une preuve simple: Prenez l'une des six personnes, l'appeler A. Soit A connaît trois des personnes qui restent, ou A ne sait pas trois des personnes restantes. Supposons que l'ancienne (la preuve est identique si l'on suppose ce dernier). Que les trois personnes que A sait être B, C, et D. Maintenant, soit deux personnes de {B, C, D} connaître (dans ce cas, nous avons un groupe de trois personnes qui se connaissent - ces deux plus un ) ou aucun de B, C, D connaître (dans ce cas, nous avons un groupe de trois personnes qui ne connaissent pas l'autre - B, C, D). CQFD.

Combinatoire extrêmes

Les types de questions abordées dans ce cas sont de la plus grande possible graphique qui satisfait certaines propriétés. Par exemple, le plus grand graphe sans triangle sur les sommets 2n est un graphe complet biparti K _{n, n.}

Combinatoire probabilistes

Voici les questions sont du type suivant: quelle est la probabilité d'une certaine propriété de graphe pour un graphe aléatoire (dans une certaine classe) Par exemple ce est le nombre moyen de triangles dans un graphe aléatoire?

Combinatoire géométriques

Combinatoire géométrique est liée à convexe et géométrie discrète. Il demande, par exemple, combien de faces de chaque dimension peut un polytope convexes ont. Propriétés métriques de polytopes jouent un rôle important ainsi, par exemple la Cauchy théorème sur la rigidité des polytopes convexes. Polytopes spéciaux sont également envisagées, comme permutoèdre, et Associaèdre Polytope Birkhoff.