Combinatoriek

Combinatoriek is een tak van de wiskunde aangaande de studie van eindige of telbare discrete structuren. Aspecten van combinatoriek omvatten het tellen van de structuren van een bepaalde soort en grootte, beslissen wanneer bepaalde criteria kan worden voldaan, en de bouw en het analyseren van voorwerpen die voldoen aan de criteria, het vinden van "grootste", "kleinste" of "optimale" voorwerpen, en het bestuderen van combinatorische structuren die ontstaan ​​in een algebraïsche context, of het toepassen van algebraïsche technieken om combinatorische problemen.

Combinatorische problemen in vele gebieden van de zuivere wiskunde, met name in de algebra, kansrekening, topologie en geometrie, en combinatoriek heeft ook vele toepassingen in wiskundige optimalisatie, informatica, ergodentheorie en statistische fysica. Veel combinatorische vragen van oudsher beschouwd, het geven van een ad hoc-oplossing voor een probleem ontstaan ​​in een aantal wiskundige context. In de latere twintigste eeuw, echter, krachtig en algemene theoretische methoden werden ontwikkeld, waardoor combinatoriek tot een zelfstandige tak van de wiskunde in zijn eigen recht. Een van de oudste en meest toegankelijke delen van combinatoriek is grafentheorie, die ook tal van natuurlijke verbindingen naar andere gebieden. Combinatoriek wordt vaak gebruikt in de informatica om formules en schattingen te verkrijgen in de analyse van algoritmen.

Een wiskundige die combinatoriek bestudeert heet een combinatorialist of combinatorist.

Geschiedenis

Basic combinatorische concepten en enumeratieve resultaten verschenen in de hele oude wereld. In de 6e eeuw voor Christus, oude Indiase arts Sushruta beweert in Sushruta Samhita dat 63 combinaties kan worden gemaakt van de 6 verschillende smaken, die één voor één, twee tegelijk, enz., Waardoor het berekenen van alle 2-1 mogelijkheden. Griekse historicus Plutarchus bespreekt een ruzie tussen Chrysippus en Hipparchus van een nogal delicaat enumeratieve probleem, dat later bleek gerelateerd te zijn aan Schröder nummers. In de Stomachion, Archimedes beschouwt een puzzel tegels.

In de Middeleeuwen, combinatoriek verder worden bestudeerd, grotendeels buiten de Europese beschaving. De Indiase wiskundige Mahavira voorzien formules voor het aantal permutaties en combinaties, en deze formules kunnen vertrouwd Indiase wiskundigen zijn al in de 6e eeuw CE. De filosoof en astronoom Rabbijn Abraham ibn Ezra richtte de symmetrie van binomiale coëfficiënten, terwijl een gesloten formule later door de Talmudist en wiskundige Levi ben Gerson werd verkregen, in 1321. Het rekenkundig driehoek een grafisch schema dat de relaties tussen de binomiale coëfficiënten werd gepresenteerd door wiskundigen in verhandelingen daterend zover terug als de 10e eeuw, en zou uiteindelijk bekend als Pascal driehoek geworden. Later, in het middeleeuwse Engeland, campanologie voorbeelden gegeven van wat nu bekend staat als Hamiltoniaanse cycli in bepaalde Cayley grafieken op permutaties.

Tijdens de Renaissance, samen met de rest van de wiskunde en de wetenschappen, combinatoriek genoten van een wedergeboorte. Werken van Pascal, Newton, Jacob Bernoulli en Euler werd fundamenteel in de opkomende veld. In de moderne tijd, het werk van JJ Sylvester en Percy MacMahon de basis gelegd voor enumeratieve en algebraïsche combinatoriek. Grafentheorie ook genoten van een explosie plaats op hetzelfde moment, met name in verband met de vier kleuren probleem.

In de tweede helft van de 20ste eeuw, combinatoriek genoten van een snelle groei, wat leidde tot oprichting van tientallen nieuwe tijdschriften en conferenties in het onderwerp. Voor een deel werd de groei gestimuleerd door nieuwe verbindingen en toepassingen op andere terreinen, variërend van algebra naar waarschijnlijkheid, van functionele analyse tot de getaltheorie, etc. Deze verbindingen werpen de grenzen tussen combinatoriek en delen van wiskunde en theoretische informatica, maar op de Tegelijkertijd leidde tot een gedeeltelijke fragmentatie van het veld.

Benaderingen en deelgebieden van de combinatoriek

Enumeratieve combinatoriek

Enumeratieve combinatorics is de klassieke gebied van combinatoriek en concentreert zich op het tellen van het aantal bepaalde combinatorische objecten. Hoewel het tellen van het aantal elementen in de set is een vrij breed wiskundig probleem, veel van de problemen die zich voordoen bij toepassingen een relatief eenvoudige combinatorische beschrijving. Fibonacci getallen is de basis voorbeeld van een probleem in enumeratieve combinatoriek. De twaalfvoudige manier biedt een uniform raamwerk voor het tellen van permutaties, combinaties en scheidingswanden.

Analytische combinatoriek

Analytische combinatoriek betreft de opsomming van combinatorische structuren met behulp van gereedschap van complexe analyse en kansrekening. In tegenstelling tot enumeratieve combinatoriek die uitdrukkelijk combinatorische formules en het genereren van functies gebruikt om de resultaten te beschrijven, analytische combinatoriek is gericht op het verkrijgen van asymptotische formules.

Partitie theorie

Partition theorie studies verschillende opsomming en asymptotische problemen met integer partities en is nauw verwant aan Q-series, bijzonderhe- orthogonale polynomen. Oorspronkelijk een deel van getaltheorie en analyse wordt nu beschouwd als een onderdeel van combinatorics of onafhankelijk veld. Het bevat de bijectieve aanpak en verschillende instrumenten in de analyse, de analytische getaltheorie, en heeft verbindingen met de statistische mechanica.

Grafentheorie

Grafieken zijn eenvoudig objecten in combinatoriek. De vragen variëren van tellen tot structurele algebraïsche vragen een combinatorische interpretatie?). Opgemerkt zij dat hoewel er zeer sterke banden tussen grafentheorie en combinatoriek deze twee soms gezien als afzonderlijke vakken.

Ontwerp theorie

Ontwerp theorie is een onderzoek van combinatorische ontwerpen die verzamelingen van subsets bepaalde doorsnede eigenschappen. Block ontwerpen zijn combinatorische ontwerpen van een speciaal type. Dit gebied is een van de oudste delen combinatoriek, zoals bij Kirkman in 1850 voorgesteld schoolmeisje probleem De oplossing van het probleem is een speciaal geval van een Steiner, dat spelen een belangrijke rol bij de indeling van eenvoudige eindige groepen. Het gebied heeft verdere verbindingen aan codering theorie en geometrische combinatoriek.

Eindige geometrie

Eindige geometrie is de studie van geometrische systemen met slechts een eindig aantal punten. Structuren die analoog zijn aan die gevonden in continue geometrieën maar gedefinieerd combinatorieel de belangrijkste punten onderzocht. Dit gebied biedt een rijke bron van voorbeelden voor Design theorie. Het moet niet worden verward met discrete geometrie.

Ordetheorie

Om de theorie is de studie van gedeeltelijk bestelde toestellen, zowel eindig en oneindig. Diverse voorbeelden van partiële opdrachten verschijnen in algebra, meetkunde, getaltheorie en de rest van combinatoriek en grafentheorie. Opmerkelijke klassen en voorbeelden van gedeeltelijke bestellingen onder roosters en Booleaanse algebra.

Matroïde theorie

Matroïde theorie abstraheert deel van de geometrie. Het bestudeert de eigenschappen van reeksen vectoren in een vectorruimte die niet afhangen van de specifieke coëfficiënten in een lineaire afhankelijkheid relatie. Niet alleen de structuur, maar ook enumeratieve eigenschappen behoren tot de theorie matroïde. Matroïde theorie werd geïntroduceerd door Hassler Whitney en bestudeerd als onderdeel van de ordetheorie. Het is thans zelfstandig vakgebied een aantal verbindingen met andere delen van combinatorics.

Extremal combinatoriek

Extremal combinatoriek studies extremal vragen op de set-systemen. De aard van de vragen in dit geval gericht zijn over de grootst mogelijke grafiek die bepaalde eigenschappen voldoet. Bijvoorbeeld, de grootste driehoek vrije grafiek 2n hoekpunten u een bipartiete grafiek Kn, n. Vaak is het te moeilijk, zelfs naar de extremen antwoord f precies te vinden en men kan alleen maar geven een asymptotische schatting.

Ramsey theorie is een ander deel van extremal combinatoriek. Het bepaalt dat elke voldoende grote configuratie een soort van orde zal bevatten. Het is een geavanceerde veralgemening van het hokje principe.

Probabilistische combinatoriek

In probabilistische combinatoriek, de vragen zijn van het volgende type: wat is de waarschijnlijkheid van een bepaalde eigenschap voor een willekeurige discrete object, zoals een willekeurige grafiek? Bijvoorbeeld, wat het gemiddelde aantal driehoeken in willekeurige grafiek? Probabilistische methoden worden ook gebruikt om het bestaan ​​van combinatorische objecten met specifieke vooraf bepaalde eigenschappen te bepalen, simpelweg door het observeren dat de waarschijnlijkheid van het willekeurig selecteren van een object met deze eigenschappen is groter dan 0. Deze aanpak bleek zeer effectief toepassingen combinatoriek en grafentheorie extrema. Een nauw verwant gebied is de studie van eindige Markov-ketens, vooral op combinatorische objecten. Ook hier probabilistische tools worden gebruikt voor het schatten van de mengtijd.

Vaak geassocieerd met Paul Erdös, die het pionierswerk op het onderwerp deed, werd probabilistische combinatoriek van oudsher gezien als een set van tools om problemen in andere delen van combinatoriek bestuderen. Echter, de groei van toepassingen in analyse algoritmen in de informatica, en klassieke waarschijnlijkheid toevoegsel en probabilistische getaltheorie, het gebied onlangs gegroeid tot een onafhankelijk gebied van combinatorics worden.

Algebraïsche combinatoriek

Algebraïsche combinatoriek is een gebied van wiskunde die methoden van de abstracte algebra, met name de theorie groep en vertegenwoordiging theorie telt, in verschillende combinatorische contexten en omgekeerd geldt combinatorische technieken om problemen in de algebra. Algebraïsche combinatoriek voortdurend uitbreiding van zijn omvang, zowel in thema's en technieken, en kan gezien worden als het gebied van de wiskunde, waar de interactie van combinatorische en algebraïsche methoden is bijzonder sterk en significant.

Combinatoriek op woorden

Combinatoriek op woorden bezig met formele talen. Het ontstond onafhankelijk in verschillende takken van de wiskunde, met inbegrip van getaltheorie, groepentheorie en waarschijnlijkheid. Het heeft toepassingen enumeratieve combinatoriek, fractal analyse, theoretische informatica, automaten theorie en taalkunde. Hoewel veel toepassingen zijn nieuw, de klassieke Chomsky-Schützenberger hiërarchie van klassen van formele grammatica is misschien wel de bekendste resultaat in het veld.

Geometrische combinatoriek

Geometrische combinatoriek is gerelateerd aan convex en discrete meetkunde, in het bijzonder polyhedrale combinatoriek. Het vraagt, bijvoorbeeld, hoeveel gezichten van elke dimensie kan een bolle polytoop hebben. Metrische eigenschappen van polytopen een belangrijke rol spelen als goed, bv de Cauchy stelling op stijfheid van bolle polytopen. Speciale polytopen worden ook beschouwd, zoals permutohedra, associahedra en Birkhoff polytopen. We moeten er rekening mee dat de combinatorische geometrie is een ouderwetse naam voor discrete geometrie.

Topologische combinatoriek

Combinatorische analogen van concepten en methoden in de topologie worden gebruikt om graafkleuring, eerlijke verdeling, wanden, gedeeltelijk besteld sets, beslisbomen, ketting problemen en discrete Morse theorie bestuderen. Het moet niet worden verward met combinatorische topologie die een oudere naam voor algebraïsche topologie.

Rekenkundige combinatoriek

Rekenkundige combinatoriek is ontstaan ​​uit de wisselwerking tussen de getaltheorie, combinatoriek, ergodentheorie en harmonische analyse. Het gaat over combinatorische schattingen geassocieerd met rekenkundige bewerkingen. Additief combinatoriek verwijst naar het speciale geval wanneer alleen de operaties van optellen en aftrekken zijn betrokken. Een belangrijke techniek in de rekenkunde combinatoriek is de ergodentheorie van dynamische systemen.

Infinitary combinatoriek

Infinitary combinatoriek, of combinatorische set theorie, is een uitbreiding van de ideeën in combinatoriek oneindig sets. Het is een deel van de set theorie, een gebied van de wiskundige logica, maar maakt gebruik van gereedschappen en ideeën van zowel de set theorie en extrema combinatoriek.

Gian-Carlo Rota gebruikte de naam continue combinatoriek om kans te beschrijven en te meten theorie, want er zijn veel overeenkomsten tussen het tellen en meten.

Aanverwante gebieden

Combinatorische optimalisering

Combinatorische optimalisering is de studie van de optimalisatie op discrete en combinatorische objecten. Het begon als een onderdeel van combinatoriek en grafentheorie, maar wordt nu gezien als een tak van de toegepaste wiskunde en informatica, gerelateerd aan operations research, algoritme theorie en computationele complexiteitstheorie.

Coderingstheorie

Codetheorie begon als een onderdeel van het ontwerp theorie met vroege combinatorische constructies van error-correcting codes. De hoofdgedachte van het onderwerp op efficiënte en betrouwbare werkwijzen voor datatransmissie te ontwerpen. Het is nu een groot gebied van de studie, een deel van de informatie theorie.

Discrete en computationele geometrie

Discrete geometrie begon ook een deel van combinatoriek, met de eerste resultaten over convexe polytopen en zoenen nummers. Met de opkomst van toepassingen van discrete geometrie computationele geometrie, deze twee gebieden gedeeltelijk samengevoegd en werd een apart vakgebied. Er blijven veel verbindingen met geometrische en topologische combinatorics, die zelf kan worden gezien als uitwassen van de vroege discrete geometrie.

Combinatoriek en dynamische systemen

Combinatorische aspecten van dynamische systemen is een opkomende gebied. Hier dynamische systemen kan worden gedefinieerd op combinatorische objecten. Zie bijvoorbeeld de grafiek dynamisch systeem.

Combinatoriek en natuurkunde

Er zijn steeds meer interactie tussen combinatoriek en natuurkunde, in het bijzonder statistische fysica. Voorbeelden zijn een exacte oplossing van de Isingmodel, en een verbinding tussen de Potts model enerzijds, en de chromatische en Tutte polynomen anderzijds.

(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha