Combinatorial
Termenul combinatorică sau combinatorică (care include și geometrie combinatorie ) se referă la domeniul matematicii care studiază seturi finite de obiecte simple (numere întregi, șiruri, noduri și conexiuni, puncte și linii, configurații discrete, seturi finite, ...) care satisfac proprietăți bine definite și practic simple.
fundal
Problemele combinatorii au fost studiate încă din cele mai vechi timpuri, dar combinația ca zonă consistentă a matematicii a fost recunoscută doar în ultimii cincizeci de ani. Un prim text care a dat greutate combinatoriei se datorează lui Netto. Combinatorica a obținut o anumită autonomie după publicarea textului Analiza combinatorie de Percy Alexander MacMahon în 1915. Importanța sa a crescut treptat în anii următori: textele lui König despre teoria graficelor și de Marshall Hall trebuie amintite.
Dezvoltarea sa a primit un impuls din opera lui Gian-Carlo Rota , care din anii 1960 a contribuit la fundamentarea teoriilor unificatoare de amploare și de mare claritate formală. O altă figură influentă a fost cea a lui Marcel-Paul Schützenberger . O acțiune diferită, dar foarte eficientă se datorează lui Paul Erdős și abilității sale de a pune și rezolva probleme, contribuțiilor sale referitoare mai ales la problemele extreme.
Descriere generala
Un aspect de importanță primară în aceste studii se referă la enumerarea configurațiilor: pentru unele exemple ale acestei probleme, a se vedea de exemplu factorial , coeficientul binomial , numerele catalane și secvența Fibonacci . Un alt aspect fundamental al combinatoriei este cel algoritmic: în primul rând, cunoașterea caracteristicilor combinatorii ale unui tip de configurație este esențială pentru identificarea mecanismelor care permit manipularea acestora; în plus, fiecare algoritm poate fi supus unor investigații combinatorii, cum ar fi cele de natură enumerativă necesare pentru evaluarea eficienței sale (a se vedea complexitatea algoritmilor ). Schema de clasificare MSC2000 pentru documentele de cercetare matematică dedică în mod explicit secțiunea de primul nivel caracterizată prin abrevierea 05-XX . Este util să indicați secțiunile de al doilea nivel ale combinatoriei, împreună cu abrevierea relativă și numărul de secțiuni de al treilea nivel atribuite acestora:
- 05Axx enumerare combinatorie (11)
- 05Bxx Desene și configurații (12)
- 05Cxx Teoria graficelor (38)
- 05Dxx Combinatorie extremă (5)
- 05Exx Combinatorie algebrică (8)
Cu toate acestea, problemele de natură combinatorie se găsesc în multe domenii ale matematicii: în teoria mulțimilor , în teoriile structurilor algebrice cu axiome slabe, în teoria câmpurilor , în teoria grupelor, în geometria proiectivă , în geometriile finite , în studiul geometriei configurații.convexe, în studiul politopilor și poliedrelor , în studiul funcțiilor speciale , în studiul sistemelor dinamice , în teoria probabilităților , în teoria optimizării , în teoria jocurilor. O considerație specială merită legătura dintre combinatorică și studiul algoritmilor care au fost deja menționați și pentru care ar trebui amintite și metodele pentru calculul simbolic automat și algebra computerizată. Legăturile dintre combinatorică și fiecare dintre zonele menționate mai sus sunt strânse și articulate: relațiile de dependență nu oferă clarificări bune, dar este mai bine să luăm în considerare stimulii și ajutoarele reciproce care se dezvoltă între aceste zone.
Chiar și atunci când se renunță la matematică pentru a parcurge disciplinele științifice, tehnologice și umaniste, se întâlnește o varietate de probleme combinatorii. Pentru acestea aveți nevoie de o listă chiar mai extinsă decât cele precedente:
- Teorii cuantice și fizica particulelor elementare ,
- Mecanica statistică și fizica materiei ,
- Chimie moleculară (în special a polimerilor ),
- Chimie combinatorie ,
- Biologie moleculară ,
- Inginerie structurală ,
- Telecomunicații , coduri autocorective și criptologie ,
- Inginerie software și măsurători software ,
- Cercetare operațională , optimizare și planificare,
- Modele de organizare economică și de afaceri,
- Probleme de transport și logistică ,
- Bibliotecariat ,
- Lexicografie și lingvistică ,
- antropologie și arheologie .
Terminologie
Unii, în locul substantivului combinator , preferă să utilizeze substantivul combinator ; în timp ce combinatorica abordează termenii cei mai folosiți în franceză ( combinatorică ), spaniolă ( combinatorică ), combinatorica abordează combinatorica englezei, Kombinatorikul german și termenii apropiați de acesta din urmă în multe alte limbi influențate de germană (v. Wikționar) ; în plus, combinatorica se apropie de substantive precum electronică și informatică și mulți experți în domeniu consideră că combinatorica trebuie considerată o disciplină care va avea un impact asupra societății comparabil cu cel al celorlalte două menționate. Pe de altă parte, pentru adjectivele corespunzătoare, prevalează combinatorial și flexiunile sale.
Pentru aspectele matematice ale acestui sector, se folosește și termenul de teoria combinatorie , pentru a sublinia disponibilitatea unui aparat teoretic capabil să prezinte într-un mod unificat multiplele probleme de natură combinatorie și metodele de domeniu general capabile să abordeze astfel de probleme. Alții, pe de altă parte, preferă să utilizeze termenul de teorii combinatorii pentru a sublinia faptul că diferitele teorii disponibile, deși sunt capabile să încadreze o gamă largă de probleme, vizează totuși probleme limitate: algebră de incidență , teorie matroidă , calcul umbral , generând funcții , teorii extreme , .... Un termen aproape echivalent este matematica discretă , un termen folosit în principal spre deosebire de matematica continuum . Cu termenul combinatoriu, însă, acest contrast nu este subliniat, în conformitate cu faptul că în studiul funcțiilor speciale , metodele combinatorii (în special cele referitoare la funcțiile generatoare) și metodele continuum sunt utilizate complementar.
Un termen similar utilizat pe scară largă este combinatorica ; apare mai presus de toate în capitolele de început ale textelor de calcul infinitezimal și introducerile la probabilitate și statistici și se referă la un cerc restrâns de subiecte (dispoziții, combinații, permutări, coeficienți binomiali și câteva altele) considerate doar ca preliminare la evoluțiile formale ulterioare . Acest calcul combinatoriu este plasat într-o poziție auxiliară în raport cu calculul infinitesimal și calculul probabilităților, dar această natură auxiliară este astăzi respinsă în mod categoric de iubitorii de combinatorică. Mulți dintre ei, pe de altă parte, afirmă esențialitatea multor evoluții din zona lor, autonomia acesteia și, de asemenea, o anumită supremație a problemelor sale.
Un termen care este plasat într-o poziție intermediară între calcul combinatorial și combinatorial este analiza combinatorie .
Exemple
Exemple de colecții de obiecte studiate în domeniul combinatoriei sunt:
- permutările de n obiecte,
- combinații cu repetarea a 5 din primele 7 numere întregi,
- grafice poliedrice ,
- pătratele magice și pătratele latine ,
- ...
Combinatorica își propune să studieze situații practice și probleme conexe la nivel matematic, ale căror aspecte esențiale pot fi exprimate cu modele discrete. Câteva exemple ale acestor situații sunt:
- dispozițiile oamenilor în jurul unei mese circulare,
- extragerea bilelor de diferite culori dintr-o urnă,
- aranjamentele pieselor de șah pe o tablă de șah,
- ...
Bibliografie
Introduceri
- Martin Aigner : Teorie combinatorie , Springer, ISBN 3-540-61787-6
- Ronald Graham , Donald Knuth , Oren Patashnik (1989): Matematică concretă , Addison-Wesley, ISBN 0-201-14236-8
- Norman L. Biggs : (2002): Matematică discretă , ed. II, Oxford Clarendon Press, ISBN 0-19-850717-8
- JH Van Lint , Robin Wilson : Un curs de combinatorie , Cambridge University Press
- GE Martin (2001): Counting: The Art of Enumerative Combinatorics , Springer
Manuale
- Ronald Graham , Martin Grötschel , László Lovász (Eds.) (1996): Handbook of Combinatorics, Volumul I , Elsevier, ISBN 0-444-82346-8
- Ronald Graham , Martin Grötschel , László Lovász (Eds.) (1996): Handbook of Combinatorics, Volumul II , Elsevier, ISBN 0-444-82351-4
- Charles J. Colburn, Jeffey H. Dinitz, eds. (1996): Manualul CRC de modele combinatorii , CRC Press, ISBN 0-8493-8948-8
- Richard P. Stanley Enumerative Combinatorics, Volumele 1 și 2 , (1997 și 1999), Cambridge University Press, ISBN 0-521-55309-1
Probleme clasice
- George E. Andrews (1976): Teoria partițiilor , Cambridge University Press
Teoria graficelor
- K. Thulasiraman, MNS Swamy (1992): Graphs: Theory and Algorithms , J.Wiley
- Béla Bollobás (1998): Teoria modernă a graficelor , Springer, ISBN 0-387-98488-7
- Lowell W. Beineke , Robin J. Wilson , Peter J. Cameron , eds (2004): Topics in Algebraic Graph Theory , Cambridge University Press
- D. Cvetković, P. Rowlison, S. Simic '(1997): Eigenspaces of Graphs , Cambridge University Press
Combinatorie algebrică
- Steve Roman (1984): Umbral calculus , Academic Press, ISBN 0-12-594380-6
- Herbert Wilf (1994): Generatingfunctionology , ed. II, Academic Press, ISBN 0-12-751956-4
- Marko Petrovsek, Herbert Wilf , Doron Zeilberger (1996): A = B , AK Peters
- Richard P. Stanley (1996): Enumerative Combinatorics, Volumul 1] , Cambridge University Press, ISBN 0-521-55309-1 Site însoțitor al celor două volume
- Richard P. Stanley (1999): Enumerative Combinatorics, Volumul 2 , Cambridge University Press, ISBN 0-521-56069-1
- François Bergeron , Gilbert Labelle , Pierre Leroux (1998): Specii combinatorii și structuri asemănătoare copacilor , Cambridge University Press, ISBN 0-521-57323-8
- Henry Crapo , Domenico Senato , eds. (2001): Combinatorie algebrică și informatică - Un tribut adus lui Gian-Carlo Rota , Springer, ISBN 88-470-0078-5
- M. Bona (2004): Combinatorics of permutations , Chapman-Hall / CRC Press
- Anders Björner , Francesco Brenti (2005): Combinatorica grupurilor Coxeter , Springer, ISBN 3-540-44238-3
Matroizi
- Neil White ed. (1986): Teoria matroidelor , Cambridge University Press
- Neil White ed. (1992): Matroid applications , Cambridge University Press
- James G. Oxley (1992): Matroid Theory . Oxford University Press, ISBN 0-19-853563-5 .
- Anders Björner , Michel Las Vergnas , Bernd Sturmfels , Neil White , Günter M. Ziegler (1993): Matroide orientate , Cambridge University Press, ISBN
- Bruno Korte , László Lovász , R. Schrader (1991): Greedoids , Springer, ISBN
Proiecte combinatorii
- Thomas Beth, Dieter Jungnickel, Hanfried Lenz (1999): Design Theory Volume 1 , ed. II, Cambridge University Press, ISBN 0-521-44432-2
- Thomas Beth, Dieter Jungnickel, Hanfried Lenz (1999): Design Theory Volume 2 , ed. II, Cambridge University Press, ISBN 0-521-77231-1
Combinatorie extremă
- Ronald Graham , B. Rothschild, JH Spencer (1980): Teoria Ramsey , J.Wiley
- BS Stechkin, VI Baranov (1995): Probleme combinatorii extreme și aplicațiile lor , Kluwer
Combinatorie de cuvinte
- M. Lothaire (1983): Combinatorics on Words , Cambridge University Press
- M. Lothaire (2002): Combinatorie algebrică pe cuvinte , Cambridge University Press
- M. Lothaire (2005): Combinatorie aplicată pe cuvinte , Cambridge University Press
Combinatorie analitică
- Philip Flajolet , Robert Sedgewick (2009): Analytic Combinatorics , Cambridge University Press, ISBN 9780521898065
Elemente conexe
- Calcul combinatorial
- Legături între combinatorică și matrice
- 05-XX inițiale ale secțiunii MSC dedicată combinatoriei.
- Glosar de combinatorie
- Principiul incluziunii-excluderii
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere în combinație
linkuri externe
- Note privind geometria combinatorie ( PDF ), pe setticarraro.gov.it .
| Controlul autorității | Tezaur BNCF 65053 · LCCN (EN) sh85028802 · GND (DE) 4164746-4 · BNF (FR) cb119470231 (dată) · BNE (ES) XX525029 (dată) |
|---|
