Combinatòria

La combinatòria és una branca de les matemàtiques pures que s'ocupa de l'estudi d'objectes discrets (i normalment també finits). Una part de la combinatòria inclou el "comptar" el nombre d'objectes que satisfan un criteri (combinatòria enumerativa), decidir quan aquest criteri es compleix, i construir i analitzar els objectes que compleixen el criteri.

Una de les àrees més antiga i més accessible de la combinatòria és la teoria de grafs.

Hi ha molts patrons i teoremes relacionats amb l'estructura d'un conjunt combinatori. Aquests normalment se centren en la partició (combinació) o partició ordenada (permutació) d'un conjunt. Un exemple senzill és saber quantes ordenacions es poden fer d'una baralla de 52 cartes. La resposta és 52! (52 factorial), que aproximadament dona 8,0658·10⁶⁷.

Definició

L'abast complet de la combinatòria no està acordat de forma universal i podem trobar discrepàncies. Segons H.J. Ryser, una definició del tema és difícil perquè creua moltes subdivisions matemàtiques. En la mesura que una àrea es pot descriure pels tipus de problemes que aborda, la combinatòria s'involucra amb:

• l'enumeració (compte) d'estructures especificades, de vegades referides com a arranjaments o configuracions en un sentit molt general, associades a sistemes finits,
• l'existència d'aquestes estructures que compleixin determinats criteris,
• la construcció d'aquestes estructures, potser de moltes maneres, i
• optimització : trobar la "millor" estructura o solució entre diverses possibilitats, ja sigui la "més gran", "la més petita" o satisfer algun altre criteri d'optimitat.

Leon Mirsky ha dit: «la combinatòria és una sèrie d'estudis vinculats que tenen alguna cosa en comú i, tanmateix, divergeixen àmpliament en els seus objectius, els seus mètodes i el grau de coherència que han assolit» Una manera de definir la combinatòria és, potser, descriure les seves subdivisions amb els seus problemes i tècniques. Aquest és l'enfocament que s'utilitza a continuació. Tanmateix, també hi ha raons purament històriques per incloure o no incloure alguns temes sota el paraigua de la combinatòria. Encara que es preocupen principalment de sistemes finits, algunes qüestions i tècniques combinatòries es poden estendre a un entorn infinit (específicament, comptable) però discret.

Història

Un exemple de canvi (amb sis campanes), un dels primers resultats no trivials de la teoria de grafs.

Conceptes combinatoris bàsics i resultats enumeratius van aparèixer al llarg del món antic. El metge indi Sushruta afirma a Sushruta Samhita que es poden fer 63 combinacions de 6 gustos diferents, agafats un a la vegada, dos a la vegada, etc., calculant així tots els 2 ⁶ − 1 possibilitats. L'historiador grec Plutarc comenta una discussió entre Crisip (segle III aC) i Hiparc (segle II aC) d'un problema enumeratiu força delicat, que més tard es va demostrar que estava relacionat amb els nombres de Schröder-Hipparchus. Abans, a l'Ostomaquion, Arquímedes (segle III aC) podria haver considerat el nombre de configuracions d'un trencaclosques de rajoles, mentre que els interessos combinatoris possiblement estaven presents en les obres perdudes d' Apol·loni.

A l'Edat Mitjana, la combinatòria es va continuar estudiant, en gran part fora de la civilització europea. El matemàtic indi Mahāvīra (c. 850 ) va proporcionar fórmules per al nombre de permutacions i combinacions, i aquestes fórmules poden haver estat familiars als matemàtics indis des del segle VI d.C. El filòsof i astrònom rabí Abraham ibn Ezra ( c. 1140 ) va establir la simetria dels coeficients binomials, mentre que una fórmula tancada va ser obtinguda més tard pel talmudista i matemàtic Levi ben Gerson (més conegut com a Gersonides), l'any 1321. El triangle aritmètic, un diagrama gràfic que mostra les relacions entre els coeficients binomials, va ser presentat pels matemàtics en tractats que dataven des del segle x, i finalment es coneixeria com el triangle de Pascal. Més tard, a l'Anglaterra medieval, la campanologia va proporcionar exemples del que ara es coneix com a cicles hamiltonians en certs gràfics de Cayley sobre permutacions.

Durant el Renaixement, juntament amb la resta de les matemàtiques i les ciències, la combinatòria va gaudir d'un renaixement. Les obres de Pascal, Newton, Jacob Bernoulli i Euler esdevenen fonamentals en el camp emergent. En temps més moderns, els treballs de JJ Sylvester (finals del segle XIX) i Percy MacMahon (inicis del segle XX) van ajudar a establir les bases de la combinatòria enumerativa i algebraica. La teoria dels grafs també va gaudir d'un creixent interès al mateix temps, especialment en relació amb el problema dels quatre colors.

A la segona meitat del segle XX, la combinatòria va gaudir d'un ràpid creixement, que va provocar l'establiment de desenes de noves revistes i conferències sobre la matèria. En part, el creixement va ser estimulat per noves connexions i aplicacions a altres camps, que van des de l'àlgebra fins a la probabilitat, des de l'anàlisi funcional fins a la teoria dels nombres, etc. i que al mateix temps va provocar una fragmentació parcial del camp.

Permutacions de subconjunts (r-permutacions o variacions)

Del conjunt de n elements només n'agafem un subconjunt, format per r elements.

Sense repeticions (r-permutació)

Una r-permutació d'un conjunt de n elements és tota ordenació formada per r dels n elements:

$P(n,r)={\frac {n!}{(n-r)!}}=n(n-1)(n-2)........(n-r+1).$

on n és el nombre total d'elements i r el nombre d'elements de la mostra (r≤n)

Amb repeticions

$n^{r}\,\!$

on n és el nombre total d'elements i r el nombre d'elements de la mostra

Si per exemple es tenen les lletres A, B, C i D i es vol saber de quantes maneres es poden ordenar en patrons de tres lletres (trigrames)

1. L'ordre importa (e.g, A-B és diferent de B-A, ambdós són inclosos com a possibilitats)
2. un objecte pot ser triat més d'una vegada (A-A és possible)

aleshores trobem que hi ha 4³ o 64 maneres. Això és així, ja que per la primera posició podem escollir qualsevol de les quatre lletres, per la segona posició també se'n pot triar qualsevol de les quatre, i per l'última posició també. Multiplicant totes les possibilitats ens dona el total (4*4*4 = 4³)

Permutacions

Es tracta de mostres d'elements que es diferencien les unes de les altres per l'ordre de col·locació dels elements. Més formalment, si A és un conjunt finit, una permutació en A és tota ordenació dels seus elements.

Hi ha dos tipus de permutacions, sense elements repetits i amb elements repetits. La funció ! és el factorial.

Sense repeticions

$P_{n}=n!=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot \ldots \cdot 3\cdot 2\cdot 1$

essent n el nombre total d'elements.

L'explicació és que quan en una permutació el subconjunt agafat és igual a la mostra, no deixa de ser un cas concret del cas anterior, el de permutacions de subconjunts. En aquest cas però, n = r (el nombre d'elements triats és igual al nombre d'elements dels que es poden triar). Aleshores tenim:

$(n)_{r}={\frac {n!}{(n-r)!}}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$

Amb repeticions

$P_{n}^{n_{1},n_{2},...n_{n}}={\frac {n!}{n_{1}!n_{2}!....n_{n}!}}$

essent n₁, n₂,....n_n les vegades que es repeteixen cada element dins la mostra i n=n₁+n₂+....+n_n.

Combinacions

Sense repeticions

Quan l'ordre no importa i cada objecte es pot triar només una vegada, el nombre de combinacions és el coeficient binomial:

$C_{n,k}={n \choose k}={{n!} \over {k!(n-k)!}}$

on n és el nombre total d'elements i k el nombre d'elements triats per cada mostra.

Amb repeticions

Quan l'ordre no importa i un objecte es pot triar més d'una vegada, el nombre de combinacions és

${{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {k}}={{n+k-1} \choose {n-1}}$

on n és el nombre total d'elements i k el nombre d'elements triats per cada mostra.

Camps relacionats

Les esferes de petons estan connectades tant amb la teoria de la codificació com amb la geometria discreta.

Optimització combinatòria

L' optimització combinatòria és l'estudi de l'optimització d'objectes discrets i combinatoris. Va començar com a part de la combinatòria i la teoria de grafs, però ara es veu com una branca de les matemàtiques aplicades i la informàtica, relacionada amb la investigació d'operacions, la teoria d'algoritmes i la teoria de la complexitat computacional.

Teoria de la codificació

La teoria de la codificació va començar com a part de la teoria del disseny amb les primeres construccions combinatòries de codis de correcció d'errors. La idea principal de l'assignatura és dissenyar mètodes eficients i fiables de transmissió de dades. Ara és un gran camp d'estudi, part de la teoria de la informació.

Geometria discreta i computacional

La geometria discreta (també anomenada geometria combinatòria) també va començar com a part de la combinatòria, amb els primers resultats sobre polítops convexos i nombres de petons . Amb l'aparició d'aplicacions de la geometria discreta a la geometria computacional, aquests dos camps es van fusionar parcialment i es van convertir en un camp d'estudi separat. Queden moltes connexions amb la combinatòria geomètrica i topològica, que es poden veure com a conseqüència de la geometria discreta primitiva.

Combinatòria i sistemes dinàmics

Els aspectes combinatoris dels sistemes dinàmics són un altre camp emergent. Aquí es poden definir sistemes dinàmics sobre objectes combinatoris. Vegeu per exemple sistema dinàmic de gràfics .

Combinatòria i física

Hi ha interaccions creixents entre la combinatòria i la física, especialment la física estadística. Els exemples inclouen una solució exacta del model d'Ising, i una connexió entre el model de Potts d'una banda, i els polinomis cromàtics i Tutte de l'altra.

Bibliografia

• Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
• Bóna, Miklós; (2011); A Walk Through Combinatorics (3rd ed.). ISBN 978-981-4335-23-2 i ISBN 978-981-4460-00-2
• Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); Handbook of Combinatorics, Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. ISBN 0-262-07169-X
• Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press. ISBN 0-8493-3986-3.
• Riordan, John (2002), An Introduction to Combinatorial Analysis, Dover, ISBN 978-0-486-42536-8
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs(#14), The Mathematical Association of America
• Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. ISBN 0-521-55309-1 i ISBN 0-521-56069-1
• Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, Nova York: Springer, ISBN 0-387-95487-2
• van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd ed., Cambridge University Press. ISBN 0-521-80340-3

Vegeu també

• Anàlisi combinatòria de dades
• Coeficient binomial
• Factorial
• Permutació
• Variació

Enllaços externs

• Combinatoria Arxivat 2022-01-17 a Wayback Machine.. "Extensiones y utilidades de HTML para la enseñanza" (castellà)
• Applied Combinatorics Open Textbook Library (anglès)
• Unit: Probability and combinatorics Khan Academy