Kombinatoryka - Combinatorics

Kombinatoryka to dziedzina matematyki zajmująca się głównie liczeniem, zarówno jako środkiem, jak i celem uzyskania wyników, oraz pewnymi własnościami struktur skończonych . Jest ściśle związany z wieloma innymi dziedzinami matematyki i ma wiele zastosowań, od logiki po fizykę statystyczną , od biologii ewolucyjnej po informatykę itp.

Pełny zakres kombinatoryki nie jest powszechnie uzgodniony. Według HJ Rysera zdefiniowanie przedmiotu jest trudne, ponieważ przecina on tak wiele matematycznych podziałów. W zakresie, w jakim obszar można opisać rodzajami problemów, którymi się zajmuje, kombinatoryka zajmuje się:

• wyliczenie (liczenie) z określonymi strukturami, czasami określane jako uzgodnień lub konfiguracjach w bardzo ogólnym sensie związane z systemami skończonych,
• istnienie takich struktur, które spełniają określone kryteria podane,
• budowa tych struktur, może na wiele sposobów, a
• optymalizacja : znalezienie „najlepszej” struktury lub rozwiązania spośród kilku możliwości, niezależnie od tego, czy jest to „największa”, „najmniejsza”, czy też spełniająca inne kryterium optymalności .

Leon Mirsky powiedział: „kombinatoryka to szereg powiązanych badań, które mają coś wspólnego, a jednak różnią się znacznie w swoich celach, metodach i stopniu spójności, jaki osiągnęli”. Jednym ze sposobów zdefiniowania kombinatoryki jest być może opisanie jej poddziałów z ich problemami i technikami. To jest podejście, które jest stosowane poniżej. Istnieją jednak również czysto historyczne powody, dla których niektóre tematy należy włączać lub nie uwzględniać pod parasolem kombinatoryki. Chociaż dotyczą głównie systemów skończonych, niektóre kombinatoryczne pytania i techniki można rozszerzyć do nieskończonego (w szczególności policzalnego ), ale dyskretnego ustawienia.

Kombinatoryka jest dobrze znana z szerokiego zakresu problemów, z jakimi się rozwiązuje. Problemy kombinatoryczne pojawiają się w wielu dziedzinach czystej matematyki , zwłaszcza w algebrze , teorii prawdopodobieństwa , topologii i geometrii , a także w wielu jej obszarach zastosowań. Wiele pytań kombinatorycznych było historycznie rozważanych w oderwaniu, dając doraźne rozwiązanie problemu pojawiającego się w pewnym kontekście matematycznym. Jednak pod koniec XX wieku rozwinęły się potężne i ogólne metody teoretyczne, czyniąc kombinatorykę samodzielną gałęzią matematyki. Jedną z najstarszych i najbardziej dostępnych części kombinatoryki jest teoria grafów , która sama w sobie ma liczne naturalne powiązania z innymi dziedzinami. Kombinatoryka jest często wykorzystywana w informatyce do uzyskiwania wzorów i szacunków w analizie algorytmów .

Matematyk który studiuje kombinatoryki nazywa się combinatorialist .

Historia

Podstawowe koncepcje kombinatoryczne i wyniki enumeratywne pojawiły się w całym starożytnym świecie . W VI wieku p.n.e. starożytny indyjski lekarz Sushruta twierdził w Sushruta Samhita, że 63 kombinacje mogą być wykonane z 6 różnych smaków, brane pojedynczo, dwa na raz itd., obliczając w ten sposób wszystkie 2 ^6-1  możliwości. Grecki historyk Plutarch omawia spór między Chrysippusem (III w. p.n.e.) a Hipparchusem (II w. p.n.e.) dotyczący dość delikatnego problemu enumeracyjnego, który później okazał się powiązany z liczbami Schrödera–Hipparcha . Wcześniej, w Stomachionie , Archimedes (III wiek p.n.e. ) mógł rozważać liczbę konfiguracji układania płytek , podczas gdy zainteresowania kombinatoryczne były prawdopodobnie obecne w zaginionych dziełach Apoloniusza .

W średniowieczu nadal studiowano kombinatorykę, głównie poza cywilizacją europejską . Indian matematyka Mahawira (ok. 850), pod warunkiem formuły liczby permutacji i kombinacji , a te wzory mogą być znane Indian matematyków już 6 ne. Filozof i astronom rabin Aben Ezra (ok. 1140), ustalono symetrię Symbol Newtona , przy zamkniętym wzór otrzymano następnie przez talmudysty i matematyka Lewiego Gerson ben (znany jako Gersonides) w 1321 arytmetyczna trójkąt-a wykres graficzny przedstawiający relacje między współczynnikami dwumianowymi — został przedstawiony przez matematyków w traktatach sięgających X wieku i ostatecznie stał się znany jako trójkąt Pascala . Później, w średniowiecznej Anglii , kampanologia dostarczyła przykładów tego, co jest obecnie znane jako cykle Hamiltona w niektórych grafach Cayleya dotyczących permutacji.

W okresie renesansu , wraz z resztą matematyki i nauk ścisłych , kombinatoryka przeżyła odrodzenie. Dzieła Pascala , Newtona , Jacoba Bernoulliego i Eulera stały się podstawą w powstającej dziedzinie. W czasach nowożytnych prace JJ Sylwestra (koniec XIX wieku) i Percy MacMahona (początek XX wieku) pomogły położyć podwaliny pod kombinatorykę enumeracyjną i algebraiczną . Teoria grafów również cieszyła się w tym samym czasie eksplozją zainteresowania, zwłaszcza w związku z problemem czterech kolorów .

W drugiej połowie XX wieku kombinatoryka rozwijała się bardzo dynamicznie, co doprowadziło do powstania kilkudziesięciu nowych czasopism i konferencji z tej dziedziny. Częściowo wzrost ten był stymulowany przez nowe powiązania i zastosowania w innych dziedzinach, od algebry po prawdopodobieństwo, od analizy funkcjonalnej po teorię liczb itp. Te powiązania zacierają granice między kombinatoryką a częściami matematyki i informatyki teoretycznej, ale na jednocześnie doprowadziło do częściowego rozdrobnienia pola.

Podejścia i poddziedziny kombinatoryki

Kombinatoryka enumeracyjna

Kombinatoryka enumeratywna jest najbardziej klasyczną dziedziną kombinatoryki i koncentruje się na liczeniu określonych obiektów kombinatorycznych. Chociaż liczenie liczby elementów w zbiorze jest dość szerokim problemem matematycznym , wiele problemów pojawiających się w aplikacjach ma stosunkowo prosty opis kombinatoryczny. Liczby Fibonacciego to podstawowy przykład problemu kombinatoryki enumeratywnej. Dwunastokrotny sposób zapewnia jednolite ramy licząc permutacji , kombinacji i partycje .

Kombinatoryka analityczna

Kombinatoryka analityczna dotyczy wyliczania struktur kombinatorycznych przy użyciu narzędzi analizy zespolonej i teorii prawdopodobieństwa . W przeciwieństwie do kombinatoryki enumeratywnej, która do opisu wyników wykorzystuje jawne formuły kombinatoryczne i funkcje generujące , kombinatoryka analityczna ma na celu uzyskanie formuł asymptotycznych .

Teoria partycji

Teoria partycji zajmuje się różnymi zagadnieniami wyliczeniowymi i asymptotycznymi związanymi z podziałami całkowitymi i jest ściśle powiązana z szeregami q , funkcjami specjalnymi i wielomianami ortogonalnymi . Pierwotnie część teorii i analizy liczb , obecnie jest uważana za część kombinatoryki lub samodzielną dziedzinę. Zawiera podejście bijektywne i różne narzędzia w analizie i analitycznej teorii liczb oraz ma powiązania z mechaniką statystyczną .

Teoria grafów

Grafy są podstawowymi obiektami kombinatoryki. Rozważania teorii grafów obejmują wyliczenia (np. liczba grafów na n wierzchołkach z k krawędziami) do istniejących struktur (np. cykle hamiltonowskie) do reprezentacji algebraicznych (np. mając graf G i dwie liczby x i y , czy Tutte wielomian T _G ( x , y ) ma interpretację kombinatoryczną?). Chociaż istnieją bardzo silne powiązania między teorią grafów a kombinatoryką, czasami traktuje się je jako odrębne przedmioty. Podczas gdy metody kombinatoryczne mają zastosowanie do wielu problemów związanych z teorią grafów, te dwie dyscypliny są zwykle używane do poszukiwania rozwiązań różnych typów problemów.

Teoria projektowania

Teoria projektu to nauka o projektach kombinatorycznych , które są zbiorami podzbiorów o określonych właściwościach przecięcia . Projekty blokowe to projekty kombinatoryczne specjalnego typu. Obszar ten jest jedną z najstarszych części kombinatoryki, tak jak w problemie uczennic Kirkmana zaproponowanym w 1850 roku. Rozwiązaniem tego problemu jest szczególny przypadek systemu Steinera , którego systemy odgrywają ważną rolę w klasyfikacji skończonych grup prostych . Obszar ma dalsze powiązania z teorią kodowania i kombinatoryką geometryczną.

Skończona geometria

Geometria skończona to nauka o układach geometrycznych mających tylko skończoną liczbę punktów. Badane są głównie struktury analogiczne do tych występujących w geometriach ciągłych ( płaszczyzna euklidesowa , rzeczywista przestrzeń rzutowa itp.), ale zdefiniowane kombinatorycznie. Obszar ten stanowi bogate źródło przykładów dla teorii projektowania . Nie należy jej mylić z geometrią dyskretną ( geometria kombinatoryczna ).

Teoria zamówień

Teoria porządku to nauka o zbiorach częściowo uporządkowanych , zarówno skończonych, jak i nieskończonych. Różne przykłady porządków cząstkowych pojawiają się w algebrze , geometrii, teorii liczb oraz w kombinatoryce i teorii grafów. Godne uwagi klasy i przykłady rzędów częściowych obejmują kraty i algebry Boole'a .

Teoria Matroid

Teoria Matroid abstraktuje część geometrii . Bada własności zbiorów (zwykle skończonych zbiorów) wektorów w przestrzeni wektorowej , które nie zależą od poszczególnych współczynników w liniowej relacji zależności . Do teorii matroid należy nie tylko struktura, ale także własności enumeratywne. Teoria Matroid została wprowadzona przez Hasslera Whitneya i badana jako część teorii porządku. Obecnie jest to samodzielny kierunek studiów z szeregiem powiązań z innymi działami kombinatoryki.

Ekstremalna kombinatoryka

Ekstremalna kombinatoryka zajmuje się badaniem ekstremalnych zagadnień dotyczących systemów zbiorów . Rodzaje pytań postawionych w tym przypadku dotyczą możliwie największego grafu, który spełnia określone właściwości. Na przykład największy graf bez trójkątów na 2n wierzchołkach jest kompletnym grafem dwudzielnym K _n,n . Często nawet znalezienie ekstremalnej odpowiedzi f ( n ) jest zbyt trudne i można jedynie oszacować asymptotycznie .

Teoria Ramseya to kolejna część ekstremalnej kombinatoryki. Stwierdza, że ​​każda wystarczająco duża konfiguracja będzie zawierać pewien porządek. Jest to zaawansowane uogólnienie zasady szufladki .

Kombinatoryka probabilistyczna

W kombinatoryce probabilistycznej pytania są następującego typu: jakie jest prawdopodobieństwo wystąpienia określonej własności dla losowego obiektu dyskretnego, takiego jak graf losowy ? Na przykład, jaka jest średnia liczba trójkątów na wykresie losowym? Metody probabilistyczne są również używane do określania istnienia obiektów kombinatorycznych o określonych właściwościach (dla których wyraźne przykłady mogą być trudne do znalezienia), po prostu obserwując, że prawdopodobieństwo losowego wyboru obiektu o tych właściwościach jest większe niż 0. Takie podejście ( często nazywane w sposób probabilistyczny ) okazały się bardzo skuteczne w zastosowaniach do ekstremalnych kombinatoryki i teorii wykresu. Ściśle pokrewnym obszarem jest badanie skończonych łańcuchów Markowa , zwłaszcza na obiektach kombinatorycznych. Tutaj ponownie stosuje się narzędzia probabilistyczne do szacowania czasu mieszania .

Często kojarzona z Paulem Erdősem , który wykonał pionierską pracę na ten temat, kombinatoryka probabilistyczna była tradycyjnie postrzegana jako zestaw narzędzi do badania problemów z innych części kombinatoryki. Jednak wraz z rozwojem zastosowań do analizy algorytmów w informatyce , a także klasycznego prawdopodobieństwa, addytywnej teorii liczb i probabilistycznej teorii liczb , obszar ten stał się ostatnio niezależną dziedziną kombinatoryki.

Kombinatoryka algebraiczna

Kombinatoryka algebraiczna to dziedzina matematyki, w której stosuje się metody algebry abstrakcyjnej , zwłaszcza teorię grup i teorię reprezentacji , w różnych kontekstach kombinatorycznych, i odwrotnie, stosuje techniki kombinatoryczne do problemów algebry . Kombinatoryka algebraiczna stale rozszerza swój zakres, zarówno w zakresie tematów, jak i technik, i może być postrzegana jako obszar matematyki, w którym interakcja metod kombinatorycznych i algebraicznych jest szczególnie silna i znacząca.

Kombinatoryka na słowach

Kombinatoryka słów zajmuje się językami formalnymi . Powstała niezależnie w ramach kilku gałęzi matematyki, w tym teorii liczb , teorii grup i prawdopodobieństwa . Ma zastosowanie w kombinatoryce enumeratywnej, analizie fraktalnej , informatyce teoretycznej , teorii automatów i językoznawstwie . Chociaż wiele zastosowań jest nowych, klasyczna hierarchia klas gramatyk formalnych Chomsky'ego-Schützenbergera jest prawdopodobnie najbardziej znanym wynikiem w tej dziedzinie.

Kombinatoryka geometryczna

Kombinatoryka geometryczna związana jest z geometrią wypukłą i dyskretną , w szczególności z kombinatoryką wielościenną . Pyta na przykład, ile ścian w każdym wymiarze może mieć wypukły polytop . Ważną rolę odgrywają również właściwości metryczne politopów, np. twierdzenie Cauchy'ego o sztywności politopów wypukłych. Rozważane są również specjalne wielościany, takie jak wielościany permutoedry , asocjaściany i wielościany Birkhoffa . Geometria kombinatoryczna to staromodna nazwa geometrii dyskretnej.

Kombinatoryka topologiczna

Kombinatoryczne analogie pojęć i metod w topologii są wykorzystywane do badania kolorowania grafów , podziału sprawiedliwego , partycji , zbiorów częściowo uporządkowanych , drzew decyzyjnych , problemów naszyjnikowych i dyskretnej teorii Morse'a . Nie należy jej mylić z topologią kombinatoryczną, która jest starszą nazwą topologii algebraicznej .

Kombinatoryka arytmetyczna

Kombinatoryka arytmetyczna powstała z połączenia teorii liczb , kombinatoryki, teorii ergodycznej i analizy harmonicznej . Chodzi o kombinatoryczne szacunki związane z operacjami arytmetycznymi (dodawanie, odejmowanie, mnożenie i dzielenie). Teoria liczb addytywnych (czasami nazywana także kombinatoryką addytywną) odnosi się do szczególnego przypadku, gdy w grę wchodzą tylko operacje dodawania i odejmowania. Jedna ważna technika arytmetycznych kombinatoryki jest ergodyczny teoria z układów dynamicznych .

Nieskończona kombinatoryka

Kombinatoryka nieskończoności, czyli teoria mnogości kombinatorycznych, jest rozszerzeniem idei kombinatoryki na zbiory nieskończone. Jest częścią teorii mnogości , obszaru logiki matematycznej , ale wykorzystuje narzędzia i idee zarówno teorii mnogości, jak i ekstremalnej kombinatoryki.

Gian-Carlo Rota użył nazwy kombinatoryka ciągła do opisania prawdopodobieństwa geometrycznego , ponieważ istnieje wiele analogii między liczeniem a miarą .

Pola pokrewne

Optymalizacja kombinatoryczna

Optymalizacja kombinatoryczna to nauka o optymalizacji obiektów dyskretnych i kombinatorycznych. Zaczęło się jako część kombinatoryki i teorii grafów, ale obecnie jest postrzegane jako gałąź matematyki stosowanej i informatyki, powiązana z badaniami operacyjnymi , teorią algorytmów i teorią złożoności obliczeniowej .

Teoria kodowania

Teoria kodowania powstała jako część teorii projektowania od wczesnych kombinatorycznych konstrukcji kodów korygujących błędy . Główną ideą przedmiotu jest projektowanie wydajnych i niezawodnych metod transmisji danych. Obecnie jest to duży kierunek studiów, część teorii informacji .

Geometria dyskretna i obliczeniowa

Geometria dyskretna (zwana również geometrią kombinatoryczną) również rozpoczęła się jako część kombinatoryki, z wczesnymi wynikami dotyczącymi politopów wypukłych i całowania liczb . Wraz z pojawieniem się zastosowań geometrii dyskretnej do geometrii obliczeniowej te dwie dziedziny częściowo się połączyły i stały się odrębnym kierunkiem studiów. Istnieje wiele powiązań z kombinatoryką geometryczną i topologiczną, które same w sobie można postrzegać jako wyrostki z wczesnej geometrii dyskretnej.

Kombinatoryka i układy dynamiczne

Kombinatoryczne aspekty układów dynamicznych to kolejna rozwijająca się dziedzina. Tutaj można definiować układy dynamiczne na obiektach kombinatorycznych. Zobacz na przykład wykres systemu dynamicznego .

Kombinatoryka i fizyka

Narastają interakcje między kombinatoryką a fizyką , zwłaszcza fizyką statystyczną . Przykłady obejmują dokładne rozwiązanie modelu Isinga i połączenie między modelem Pottsa z jednej strony, a wielomianami chromatycznymi i Tutte z drugiej strony.

Zobacz też

Uwagi

Bibliografia

• Björnera, Andersa; i Stanley, Richard P.; (2010); Kombinatoryczne Miscellany
• Bona, Miklós; (2011); Spacer po kombinatoryce (wydanie trzecie) . ISBN  978-981-4335-23-2 , 978-981-4460-00-2
• Graham, Ronald L.; Groetschel, Martin; i Lovász, László; wyd. (1996); Handbook of Combinatorics , tomy 1 i 2. Amsterdam, Holandia i Cambridge, MA: Elsevier (północna Holandia) i MIT Press. ISBN  0-262-07169-X
• Lindner, Karol C.; i Rodger, Christopher A.; wyd. (1997); Teoria Projektu , CRC-Press; 1. wydanie (1997). ISBN  0-8493-3986-3 .
• Riordan, John (2002) [1958], Wprowadzenie do analizy kombinatorycznej , Dover, ISBN 978-0-486-42536-8
• Ryser, Herbert John (1963), Matematyka kombinatoryczna , Monografie matematyczne Carusa (nr 14), The Mathematical Association of America
• Stanley, Richard P. (1997, 1999); Enumerative Combinatorics , tomy 1 i 2 , Cambridge University Press . ISBN  0-521-55309-1 , 0-521-56069-1
• van Lint, Jacobus H.; i Wilson, Richard M.; (2001); Kurs kombinatoryki , wydanie drugie, Cambridge University Press. ISBN  0-521-80340-3

Linki zewnętrzne

• „Analiza kombinatoryczna” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Analiza kombinatoryczna – artykuł w Encyclopædia Britannica Eleventh Edition
• Combinatorics , artykuł MathWorld z wieloma odniesieniami.
• Kombinatoryka , z portalu MathPages.com .
• Hyperbook of Combinatorics , zbiór linków do artykułów matematycznych.
• The Two Cultures of Mathematics WT Gowersa, artykuł o rozwiązywaniu problemów a budowaniu teorii.
• „Słownik pojęć w kombinatoryce”
• Lista oprogramowania kombinatorycznego i baz danych