Geschiedenis van de combinatoriek

Het wiskundige discipline van de combinatoriek werd in talloze oude samenlevingen in verschillende mate bestudeerd. De studie ervan in Europa begon met het werk van Fibonacci in de 13e eeuw na Christus, dat Arabische en Indiase ideeën introduceerde. Combinatoriek wordt in de moderne tijd nog steeds bestudeerd.

Vroegste gegevens

Een deel van de Rhind-papyrus.

Het vroegste geregistreerde gebruik van combinatorische technieken komt uit probleem 79 van de Rhind-papyrus. De papyrus dateert uit de 16e eeuw voor Christus. Het probleem heeft betrekking op een bepaalde meetkundige reeks. Het vertoont overeenkomsten met het probleem van Fibonacci om het aantal composities van enen en tweeën te tellen die optellen tot een bepaald totaal.

In Griekenland schreef Plutarchus dat Xenocrates het aantal verschillende lettergrepen ontdekte dat mogelijk was in de Griekse taal. Dit zou de eerste ooit geregistreerde poging zijn geweest om een moeilijk probleem in permutaties en combinaties op te lossen. De bewering is echter onwaarschijnlijk: dit is een van de weinige vermeldingen van combinatoriek in Griekenland. Het aantal dat ze vonden was 1,002x10¹² en dit lijkt te rond om meer dan een gok te zijn.

Later wordt er melding gemaakt van een woordenwisseling tussen Chrysippos (3e eeuw v.Chr.) en Hipparchus (2e eeuw v.Chr.) over een nogal delicaat opsommingsprobleem, waarvan later werd aangetoond dat het verband hield met de Schröder-Hipparchus-getallen. Er zijn ook aanwijzingen dat Archimedes (3e eeuw v.Chr.) in de Stomachion de configuraties van een tegelpuzzel overwoog, terwijl er mogelijk combinatorische interesses aanwezig waren in verloren gegane werken van Apollonius van Perga.

In India werd in de Bhagavati Sutra voor het eerst melding gemaakt van een combinatorisch probleem. Het probleem vroeg hoeveel mogelijke smaakcombinaties er mogelijk waren door smaken te selecteren in eenheden, tweeën, drieën, enz. uit een selectie van zes verschillende smaken. De Bhagavati is ook de eerste tekst waarin de binomiaalcoëfficiënt wordt genoemd. In de tweede eeuw voor Christus nam Pingala een opsommingsprobleem op in de Chanda Sutra (ook Chandahsutra), waarin werd gevraagd op hoeveel manieren een metrum van zes lettergrepen kon worden gemaakt uit korte en lange noten. Pingala vond het aantal meters dat $n$ lange noten en $k$ korte aantekeningen had; dit komt overeen met het vinden van de binomiale coëfficiënten.

De ideeën van de Bhagavati werden in 850 na Christus veralgemeend door de Indiase wiskundige Mahavira, en Pingala's werk op het gebied van prosodie werd in 1100 na Christus uitgebreid door Bhāskara II en Hemacandra. Bhaskara was de eerste bekende persoon die de veralgemeende keuzefunctie ontdekte, hoewel Brahmagupta dit misschien eerder wist. Hemacandra vroeg hoeveel meters er bestonden van een bepaalde lengte als een lange noot als twee keer zo lang werd beschouwd als een korte noot, wat gelijk staat aan het vinden van de Fibonacci-getallen.

Een hexagram

Het oude Chinese waarzeggerijboek Boek der Veranderingen beschrijft een hexagram als een permutatie met herhalingen van zes regels, waarbij elke regel een van twee toestanden kan hebben: ononderbroken of onderbroken. Door hexagrammen op deze manier te beschrijven, stellen ze vast dat er $2^{6}=64$ mogelijke hexagrammen zijn. Een Chinese monnik heeft mogelijk rond 700 na Christus ook het aantal configuraties geteld voor een bordspel dat vergelijkbaar is met Go. Hoewel China relatief weinig vooruitgang boekte op het gebied van enumeratieve combinatoriek, losten ze rond 100 na Christus het probleem van het Lo Shu-plein op. Dit is het combinatorische ontwerpprobleem van het normale magisch vierkant van orde drie. Magische vierkanten bleven een interesse van China. Ze begonnen hun originele $3\times 3$-vierkant te veralgemenen tussen 900 en 1300 na Christus. China correspondeerde in de 13e eeuw met het Midden-Oosten over dit probleem. Het Midden-Oosten leerde ook over binominale coëfficiënten uit Indiaas werk en ontdekte het verband met de expansie van veeltermen. Het werk van de hindoes beïnvloedde de Arabieren, zoals blijkt uit het werk van al-Khalil ibn Ahmad, die de mogelijke rangschikking van letters om lettergrepen te vormen overwoog. Zijn berekeningen tonen inzicht in permutaties en combinaties. In een passage uit het werk van de Arabische wiskundige Umar al-Khayyami, die dateert van rond 1100, wordt bevestigd dat de Hindoes kennis hadden van binominale coëfficiënten, maar ook dat hun methoden het Midden-Oosten bereikten.

Al-Karaji (ca.953-1029) schreef over de binomiale stelling en de driehoek van Pascal. In een nu verloren gegaan werk dat alleen bekend is uit een later citaat van al-Samaw'al, introduceerde Al-Karaji het idee van argumenteren door middel van wiskundige inductie.

De filosoof en astronoom Rabbi Abraham ibn Ezra (ca. 1140) telde de permutaties met herhalingen in de vocalisatie van de Goddelijke Naam. Hij stelde ook de symmetrie van binominale coëfficiënten vast, terwijl later in 1321 een gesloten formule werd verkregen door de talmoedist en wiskundige Levi ben Gerson (beter bekend als Gersonides). De rekenkundige driehoek – een grafisch diagram dat de relaties tussen de binominale coëfficiënten laat zien – werd door wiskundigen gepresenteerd in verhandelingen die teruggaan tot de 10e eeuw, en zou uiteindelijk bekend worden als de driehoek van Pascal. In het middeleeuwse Engeland leverde de campanologie later voorbeelden van wat nu bekend staat als Hamiltonpaden in bepaalde Cayley-grafen over permutaties.

Combinatoriek in het Westen

Combinatoriek kwam in de 13e eeuw naar Europa via de wiskundigen Fibonacci en Jordanus de Nemore. Fibonacci's Liber Abaci introduceerde veel van de Arabische en Indiase ideeën in het Europees continent, inclusief die van de Fibonacci-getallen. De Nemore was de eerste persoon die de binominale coëfficiënten in een driehoek rangschikte, zoals hij deed in stelling 70 van De Arithmetica. Dit gebeurde ook in het Midden-Oosten in 1265, en in China rond 1300. Tegenwoordig staat deze driehoek bekend als de driehoek van Pascal.

De bijdrage van Pascal aan de driehoek die zijn naam draagt, komt voort uit zijn werk aan formele bewijzen hierover, en de verbanden die hij legde tussen de driehoek van Pascal en de kansrekening. Uit een brief die Leibniz aan Daniel Bernoulli stuurde, leren we dat Leibniz in de 17e eeuw formeel de wiskundige theorie van partities bestudeerde, hoewel hij hierover geen formeel werk heeft gepubliceerd. Samen met Leibniz publiceerde Pascal in 1666 De Arte Combinatoria. Pascal en Leibniz worden beschouwd als de grondleggers van de moderne combinatoriek.

Zowel Pascal als Leibniz begrepen dat de binominale expansie equivalent was aan de keuzefunctie. Het idee dat algebra en combinatoriek met elkaar correspondeerden, werd uitgebreid door De Moivre, die de expansie van een multinomiaal vond. De Moivre vond ook de formule voor verstoringen met behulp van het principe van inclusie en exclusie, een methode die verschilt van Nikolaus Bernoulli, die deze eerder had gevonden. De Moivre slaagde er ook in de binomiale coëfficiënten en faculteit te benaderen, en vond een gesloten vorm voor de Fibonacci-getallen door voortbrengende functies uit te vinden.

In de 18e eeuw werkte Euler aan problemen van de combinatoriek, en verschillende waarschijnlijkheidsproblemen die verband houden met de combinatoriek. Problemen waar Euler aan werkte, zijn onder meer de paardenrondgang, het Latijns vierkant, de euleriaanse getallen en andere. Om het probleem van de zeven bruggen van Koningsbergen op te lossen, vond hij de grafentheorie uit, wat ook leidde tot de vorming van de topologie. Ten slotte deed hij baanbrekend werk met partities door het gebruik van voortbrengende functies.

Hedendaagse combinatoriek

In de 19e eeuw ontstonden de onderwerpen van de partieel geordende verzamelingen en de tralietheorie in het werk van Dedekind, Peirce en Schröder. Het waren echter het baanbrekende werk van Garrett Birkhoff in zijn boek Lattice Theory, gepubliceerd in 1967, en het werk van John von Neumann die de onderwerpen werkelijk vastlegden. In de jaren dertig verklaarden Hall (1936) en Weisner (1935) onafhankelijk van elkaar de algemene möbius-inversieformule.

In de tweede helft van de 20e eeuw maakte combinatoriek een snelle groei door, wat leidde tot de oprichting van tientallen nieuwe tijdschriften en conferenties over het onderwerp. Deels werd de groei gestimuleerd door nieuwe verbindingen en toepassingen met andere vakgebieden, variërend van algebra tot kansrekening, van functionaalanalyse tot getaltheorie, enz. Door deze verbindingen vervaagden de grenzen tussen combinatoriek en andere delen van de wiskunde en de theoretische informatica, maar tegelijkertijd leidde dit tot een gedeeltelijke versplintering van het vakgebied. Een aantal subdisciplines die ontstonden in de 20e eeuw zijn extremale combinatoriek, analytische combinatoriek en Ramsey-theorie.

In 1964 introduceerde Gian-Carlo Rota's On the Foundations of Combinatorial Theory I. Theory of Möbius Functions de theorie van partieel geordende verzamelingen- en tralietheorie als theorieën in de combinatoriek. Richard P. Stanley heeft een grote impact gehad in de hedendaagse combinatoriek vanwege zijn werk in de matroïdetheorie, voor de introductie van Zeta-veeltermen, voor het expliciet definiëren van Euleriaanse posets, het ontwikkelen van de theorie van binominale posets samen met Rota en Peter Doublet, en meer. Paul Erdős heeft door de eeuw heen baanbrekende bijdragen geleverd aan de combinatoriek en gedeeltelijk voor deze bijdragen de Wolf-prijs gewonnen.