Combinatòria
El terme combinatòria o combinatòria (que també inclou geometria combinatòria ) fa referència al camp de les matemàtiques que estudia conjunts finits d’objectes simples (enters, cadenes, nodes i connexions, punts i línies, configuracions discretes, conjunts finits, ...) que satisfan propietats ben definides i bàsicament senzilles.
Antecedents
Els problemes combinatoris s’han estudiat des de temps remots, però la combinatòria com a àrea consistent de les matemàtiques només s’ha reconegut en els darrers cinquanta anys. Un primer text que va donar pes a la combinatòria es deu a Netto. La combinatòria va aconseguir una certa autonomia després de la publicació del text Anàlisi combinatòria de Percy Alexander MacMahon el 1915. La seva importància va anar creixent progressivament en els anys següents: cal recordar els textos de König sobre teoria de gràfics i de Marshall Hall.
El seu desenvolupament ha rebut un impuls de l'obra de Gian-Carlo Rota , que des dels anys seixanta ha contribuït a la base d'unificar teories d'ampli abast i gran claredat formal. Una altra figura influent va ser la de Marcel-Paul Schützenberger . Una acció diferent però molt eficaç es deu a Paul Erdős i a la seva capacitat per plantejar i resoldre problemes, les seves contribucions sobre sobretot problemes extrems.
Descripció general
Un aspecte d’importància primordial en aquests estudis és l’ enumeració de configuracions: per a alguns exemples d’aquest problema, vegeu, per exemple, el factorial , el coeficient binomial , els nombres catalans i la seqüència de Fibonacci . Un altre aspecte fonamental de la combinatòria és l’algorítmic: en primer lloc, el coneixement de les característiques combinatòries d’un tipus de configuració és essencial per identificar els mecanismes que permeten la seva manipulació; a més, cada algorisme pot ser objecte d'investigacions combinatòries, com ara les de caràcter enumeratiu necessàries per avaluar la seva eficiència (vegeu la complexitat dels algorismes ). L’ esquema de classificació MSC2000 per a documents de recerca matemàtica dedica explícitament la secció de primer nivell caracteritzada per l’abreviatura 05-XX . És útil indicar les seccions de segon nivell de la combinatòria, juntament amb l'abreviatura relativa i el nombre de seccions de tercer nivell que se'ls atribueix:
- 05Axx Enumeració combinatòria (11)
- 05Bxx Dibuixos i configuracions (12)
- 05Cxx Teoria de gràfics (38)
- 05Dxx extremal combinatòria (5)
- 05Exx Combinatòria algebraica (8)
Tanmateix, problemes de naturalesa combinatòria es troben en molts camps de les matemàtiques: en teoria de conjunts , en teories d’estructures algebraiques amb axiomes febles, en teoria de camps , en teoria de grups, en geometria projectiva , en geometries finites , en l’estudi de les geometries configuracions.convexes, en l'estudi de politops i poliedres , en l'estudi de funcions especials , en l'estudi de sistemes dinàmics , en teoria de probabilitats , en teoria d' optimització , en teoria de jocs. Una consideració particular mereix la connexió entre la combinatòria i l’estudi d’algoritmes que ja s’han esmentat i per als quals també s’han de recordar els mètodes per al càlcul simbòlic automàtic i l’àlgebra informàtica. Els vincles entre la combinatòria i cadascuna de les àrees esmentades són estretes i articulades: les relacions de dependència no aporten bones aclariments, però és més adequat tenir en compte els estímuls i ajudes mútues que es desenvolupen entre aquestes àrees.
Fins i tot quan es deixa les matemàtiques per desplaçar-se per les disciplines científiques, tecnològiques i humanístiques, es troba una varietat de problemes combinatoris. Per a això, necessiteu una llista encara més extensa que les anteriors:
- Teories quàntiques i física de partícules elementals ,
- Mecànica estadística i física de la matèria ,
- Química molecular (especialment dels polímers ),
- Química combinatòria ,
- Biologia molecular ,
- Enginyeria estructural ,
- Telecomunicacions , codis autocorrectius i criptologia ,
- Enginyeria de programari i mètriques de programari ,
- Investigació , optimització i planificació d’ operacions ,
- Models d'organització econòmica i empresarial,
- Problemes de transport i logística ,
- Bibliotecària ,
- Lexicografia i lingüística ,
- antropologia i arqueologia .
Terminologia
Alguns, en lloc del nom combinatori , prefereixen utilitzar el nom combinatori ; mentre que la combinatòria s'acosta als termes més utilitzats en francès ( combinatòria ), espanyol ( combinatòria ), la combinatòria s'apropa a la combinatòria de l'anglès, el Kombinatorik de l'alemany i els termes propers a aquest últim de moltes altres llengües influïdes per l'alemany (v. Viccionari) ; a més, la combinatòria s’acosta a substantius com electrònica i informàtica i molts experts en la matèria creuen que la combinatòria s’ha de considerar una disciplina que tindrà un impacte en la societat comparable al de les altres dues esmentades. Per als adjectius corresponents, en canvi, prevalen definitivament la combinatòria i les seves flexions.
Per als aspectes matemàtics d’aquest sector, també s’utilitza el terme teoria combinatòria , per subratllar la disponibilitat d’un aparell teòric capaç de presentar de manera unificada els múltiples problemes de naturalesa combinatòria i els mètodes d’abast general capaços d’abordar aquests problemes. D’altres, en canvi, prefereixen utilitzar el terme teories combinatòries per subratllar el fet que les diferents teories disponibles, tot i que són capaces d’emmarcar una àmplia gamma de problemes, estan dirigides a qüestions limitades: àlgebra d’incidència , teoria matroide , càlcul umbral , funcions generadores , teories extremals , .... Un terme gairebé equivalent és matemàtica discreta , un terme utilitzat principalment en contrast amb les matemàtiques contínues . Tanmateix, amb el terme combinatori, aquest contrast no es subratlla, d'acord amb el fet que en l'estudi de funcions especials , s'utilitzen mètodes combinatoris (en particular els relacionats amb funcions generadores) i mètodes de continu.
Un terme similar àmpliament utilitzat és combinatòria ; apareix sobretot als capítols inicials dels textos de càlcul infinitesimal i a les introduccions a la probabilitat i a les estadístiques i es refereix a un petit cercle de temes (disposicions, combinacions, permutacions, coeficients binomials i alguns altres) considerats només com a preliminars als desenvolupaments formals posteriors. . Aquest càlcul combinatori es situa en una posició auxiliar pel que fa al càlcul infinitesimal i al càlcul de probabilitats, però aquesta naturalesa auxiliar és avui totalment rebutjada pels amants de la combinatòria. Molts d'ells, en canvi, afirmen l'essencialitat de molts desenvolupaments de la seva àrea, la seva autonomia i també una certa primacia dels seus problemes.
Un terme que es col·loca en una posició intermèdia entre càlcul combinatori i combinatori és l’ anàlisi combinatòria .
Exemples
Alguns exemples de col·leccions d'objectes estudiats en el camp de la combinatòria són:
- les permutacions de n objectes,
- combinacions amb repetició de 5 dels primers 7 enters,
- gràfics polièdrics ,
- les places màgiques i les places llatines ,
- ...
La combinatòria té com a objectiu estudiar situacions pràctiques i problemes relacionats a nivell matemàtic, els aspectes essencials dels quals es poden expressar amb models discrets. Alguns exemples d’aquestes situacions són:
- les disposicions de les persones al voltant d’una taula circular,
- l'extracció de boles de diferents colors d'una urna,
- els arranjaments de les peces d' escacs en un tauler d'escacs,
- ...
Bibliografia
Introduccions
- Martin Aigner : teoria combinatòria , Springer, ISBN 3-540-61787-6
- Ronald Graham , Donald Knuth , Oren Patashnik (1989): Matemàtiques concretes , Addison-Wesley, ISBN 0-201-14236-8
- Norman L. Biggs : (2002): Matemàtiques discretes , II ed., Oxford Clarendon Press, ISBN 0-19-850717-8
- JH Van Lint , Robin Wilson : Un curs de combinatòria , Cambridge University Press
- GE Martin (2001): Counting: The Art of Enumerative Combinatorics , Springer
Manuals
- Ronald Graham , Martin Grötschel , László Lovász (Eds.) (1996): Manual de combinatòria, volum I , Elsevier, ISBN 0-444-82346-8
- Ronald Graham , Martin Grötschel , László Lovász (Eds.) (1996): Manual de combinatòria, volum II , Elsevier, ISBN 0-444-82351-4
- Charles J. Colburn, Jeffey H. Dinitz, eds. (1996): The CRC handbook of Combinatorial Designs , CRC Press, ISBN 0-8493-8948-8
- Richard P. Stanley Enumerative Combinatorics, volums 1 i 2 , (1997 i 1999), Cambridge University Press, ISBN 0-521-55309-1
Problemes clàssics
- George E. Andrews (1976): The Theory of Partitions , Cambridge University Press
Teoria de gràfics
- K. Thulasiraman, MNS Swamy (1992): Gràfics: teoria i algorismes , J.Wiley
- Béla Bollobás (1998): Modern Graph Theory , Springer, ISBN 0-387-98488-7
- Lowell W. Beineke , Robin J. Wilson , Peter J. Cameron , eds (2004): Temes en teoria de gràfics algebraics , Cambridge University Press
- D. Cvetković, P. Rowlison, S. Simic '(1997): Eigenspaces of Graphs , Cambridge University Press
Combinatòria algebraica
- Steve Roman (1984): Càlcul Umbral , Academic Press, ISBN 0-12-594380-6
- Herbert Wilf (1994): Generatingfunctionology , II ed., Academic Press, ISBN 0-12-751956-4
- Marko Petrovsek, Herbert Wilf , Doron Zeilberger (1996): A = B , AK Peters
- Richard P. Stanley (1996): Enumerative Combinatorics, Volum 1] , Cambridge University Press, ISBN 0-521-55309-1 Lloc d'acompanyament dels dos volums
- Richard P. Stanley (1999): Enumerative Combinatorics, volum 2 , Cambridge University Press, ISBN 0-521-56069-1
- François Bergeron , Gilbert Labelle , Pierre Leroux (1998): espècies combinatòries i estructures semblants als arbres , Cambridge University Press, ISBN 0-521-57323-8
- Henry Crapo , Domenico Senato , eds. (2001): Combinatòria algebraica i informàtica - Un homenatge a Gian-Carlo Rota , Springer, ISBN 88-470-0078-5
- M. Bona (2004): Combinatòria de permutacions , Chapman-Hall / CRC Press
- Anders Björner , Francesco Brenti (2005): Combinatòria de grups Coxeter , Springer, ISBN 3-540-44238-3
Matroides
- Neil White ed. (1986): Teoria dels matroides , 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): Matroids orientats , Cambridge University Press, ISBN
- Bruno Korte , László Lovász , R. Schrader (1991): Greedoids , Springer, ISBN
Dissenys combinatoris
- Thomas Beth, Dieter Jungnickel, Hanfried Lenz (1999): Teoria del disseny Volum 1 , II ed., Cambridge University Press, ISBN 0-521-44432-2
- Thomas Beth, Dieter Jungnickel, Hanfried Lenz (1999): Teoria del disseny Volum 2 , II ed., Cambridge University Press, ISBN 0-521-77231-1
Combinatòria extrema
- Ronald Graham , B. Rothschild, JH Spencer (1980): Teoria de Ramsey , J.Wiley
- BS Stechkin, VI Baranov (1995): Problemes combinatoris extrems i les seves aplicacions , Kluwer
Combinatòria de paraules
- M. Lothaire (1983): Combinatorics on Words , Cambridge University Press
- M. Lothaire (2002): Algebraic combinatorics on Words , Cambridge University Press
- M. Lothaire (2005): combinatòria aplicada sobre paraules , Cambridge University Press
Combinatòria analítica
- Philip Flajolet , Robert Sedgewick (2009): Analytic Combinatorics , Cambridge University Press, ISBN 9780521898065
Articles relacionats
- Càlcul combinatori
- Enllaços entre combinatòria i matrius
- 05-XX inicials de la secció del MSC dedicada a la combinatòria.
- Glossari de combinatòria
- Principi d’inclusió-exclusió
Altres projectes
-
Wikimedia Commons conté imatges o altres fitxers en combinatòria
Enllaços externs
- Notes sobre geometria combinatòria ( PDF ), a setticarraro.gov.it .
| Control de l'autoritat | Thesaurus BNCF 65053 · LCCN (EN) sh85028802 · GND (DE) 4164746-4 · BNF (FR) cb119470231 (data) · BNE (ES) XX525029 (data) |
|---|
