Combinatòria

branca de les matemàtiques discretes

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.[1][2]

Una de les àrees més antiga i més accessible de la combinatòria és la teoria de grafs.[3][4][5]

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·1067.

Definició

modifica

L'abast complet de la combinatòria no està acordat de forma universal i podem trobar discrepàncies.[6] Segons H.J. Ryser, una definició del tema és difícil perquè creua moltes subdivisions matemàtiques.[7] 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» [8] 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.[9] 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

modifica
 
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 6 − 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.[10][11][12] Abans, a l'Ostomaquion, Arquímedes (segle III aC) podria haver considerat el nombre de configuracions d'un trencaclosques de rajoles, [13] mentre que els interessos combinatoris possiblement estaven presents en les obres perdudes d' Apol·loni.[14][15]

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,[16] i aquestes fórmules poden haver estat familiars als matemàtics indis des del segle VI d.C.[17] 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.[18] 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.[19][20]

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.[21] 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)

modifica

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

Sense repeticions (r-permutació)

modifica

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

 


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

Amb repeticions

modifica
 

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 43 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 = 43)

Permutacions

modifica

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

modifica
 

essent n el nombre total d'elements.[3]

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:

 

Amb repeticions

modifica
 

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

Combinacions

modifica

Sense repeticions

modifica

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

 

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

Amb repeticions

modifica

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

 

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

Camps relacionats

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

Optimització combinatòria

modifica

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ó

modifica

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

modifica

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

modifica

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

modifica

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.

Referències

modifica
  1. «cursos:curriculum:eso_btx:dsma:modul_6:practica_2 [Formació del professorat]». [Consulta: 17 gener 2022].
  2. «ÍNDICE». [Consulta: 17 gener 2022].
  3. 3,0 3,1 3,2 «combinatorics | mathematics | Britannica» (en anglès). [Consulta: 17 gener 2022].
  4. Combinatorics a MathWorld (anglès)
  5. «Combinatorics | World of Mathematics» (en anglès). [Consulta: 17 gener 2022].
  6. Pak, Igor. «What is Combinatorics?». Arxivat de l'original el 17 October 2017. [Consulta: 1r novembre 2017].
  7. Ryser 1963
  8. "Book Review", Bulletin of the American Mathematical Society, doi:10.1090/S0273-0979-1979-14606-8, <https://www.ams.org/journals/bull/1979-01-02/S0273-0979-1979-14606-8/S0273-0979-1979-14606-8.pdf>. Consulta: 4 febrer 2021
  9. Rota, Gian Carlo. Discrete Thoughts. Birkhaüser, 1969, p. 50. DOI 10.1007/978-0-8176-4775-9. ISBN 978-0-8176-4775-9. 
  10. Acerbi, F. Archive for History of Exact Sciences, 57, 6, 2003, pàg. 465–502. DOI: 10.1007/s00407-003-0067-0 [Consulta: 12 març 2021].
  11. Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
  12. Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei The American Mathematical Monthly, 105, 5, 1998, pàg. 446. DOI: 10.1080/00029890.1998.12004906.
  13. Netz, R.; Acerbi, F.; Wilson, N. Sciamvs, 5, pàg. 67–99 [Consulta: 12 març 2021].
  14. Hogendijk, Jan P. Archive for History of Exact Sciences, 35, 3, 1986, pàg. 187–253. DOI: 10.1007/BF00357307. ISSN: 0003-9519. JSTOR: 41133783 [Consulta: 26 març 2021].
  15. Huxley, G. Greek, Roman, and Byzantine Studies, 8, 3, 1967, pàg. 203 [Consulta: 26 març 2021].
  16. Puttaswamy, Tumkur K. «The Mathematical Accomplishments of Ancient Indian Mathematicians». A: Selin. Mathematics Across Cultures: The History of Non-Western Mathematics. Netherlands: Kluwer Academic Publishers, 2000, p. 417. ISBN 978-1-4020-0260-1. 
  17. Biggs, Norman L. Historia Mathematica, 6, 2, 1979, pàg. 109–136. DOI: 10.1016/0315-0860(79)90074-0 [Consulta: free].
  18. , ISBN 978-1-4832-1863-2, <https://books.google.cat/books?id=2ZbiBQAAQBAJ&pg=PA35>. Consulta: 25 gener 2015. (Translation from 1967 Russian ed.)
  19. White, Arthur T. The American Mathematical Monthly, 94, 8, 1987, pàg. 721–746. DOI: 10.1080/00029890.1987.12000711.
  20. White, Arthur T. The American Mathematical Monthly, 103, 9, 1996, pàg. 771–778. DOI: 10.1080/00029890.1996.12004816.
  21. See Journals in Combinatorics and Graph Theory Arxivat 2021-02-17 a Wayback Machine.
  22. «combinatorics - Problems of enumeration | Britannica» (en anglès). [Consulta: 17 gener 2022].

Bibliografia

modifica

Vegeu també

modifica

Enllaços externs

modifica