combinatoriek

Combinatoriek is de wiskundige discipline die zich bezighoudt met tellende vraagstukken, constructie en de studie van discrete structuren. Centrale vragen gaan over hoeveel objecten er bestaan onder bepaalde regels, op hoeveel manieren objecten kunnen worden gerangschikt of geselecteerd, en welke eigenschappen deze structuren vertonen. Veelvoorkomende objecten zijn verzamelingen, partities, grafen en alfabetten van symbolen. De methode combineert tellingstechnieken met constructie en classificatie.

Historisch gezien vindt combinatoriek wortels in de 18e eeuw met Euler, maar pas in de 20e eeuw werd het als zelfstandig vakgebied ontwikkeld, mede door wiskundigen als Pólya en Erdős. Later ontstonden onder meer grafentheorie, algebraïsche combinatoriek en probabilistische methoden als belangrijke subvelden. De ontwikkeling ging gepaard met een groeiende collectie technieken om generaliseerbare tellingen en constructies te verkrijgen.

De belangrijkste gebieden omvatten enumeratieve combinatoriek (telproblemen), grafen en grafentheorie, algebraïsche combinatoriek en de probabilistische methode. Technieken bestaan onder meer uit recursie, inclusie-exclusie, permutatie- en combinatorieberekeningen, generating functions en partitie-uitdrukkingen. Een dominante benadering is het modelleren van problemen met grafische voorstellingen en het bestuderen van symmetrie en invarianten via algebra.

Toepassingen zijn onder meer in informatica (algoritmen en complexiteit), codering en foutcorrectie, cryptografie, netwerken, planning en optimalisatie, en statistische modellering.

Basisconcepten omvatten permutaties, combinaties, partities en binomiale coëfficiënten. De binomiale stelling, het Pascal-driehoekmodel en generating functions illustreren de relaties tussen telling en algebra. De probabilistische methode toont bestaan met behulp van willekeurige constructies.