Combinatòria

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca

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

Icona de la lupa mgx2.svg El mateix tema en detall: Història de la combinatòria .

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:

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:

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:

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

Manuals

Problemes clàssics

Teoria de gràfics

Combinatòria algebraica

Matroides

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

Articles relacionats

Altres projectes

Enllaços externs

Control de l'autoritat Thesaurus BNCF 65053 · LCCN (EN) sh85028802 · GND (DE) 4164746-4 · BNF (FR) cb119470231 (data) · BNE (ES) XX525029 (data)
Matemàtiques Portal de matemàtiques : accediu a les entrades de Wikipedia relacionades amb les matemàtiques