Vés al contingut

Combinatòria: diferència entre les revisions

De la Viquipèdia, l'enciclopèdia lliure
Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
VP:10.000 - Ampliació article
VP:10.000 - Ampliació article
Línia 14: Línia 14:


[[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» <ref>{{Citation|title=Book Review|url=https://www.ams.org/journals/bull/1979-01-02/S0273-0979-1979-14606-8/S0273-0979-1979-14606-8.pdf|journal=Bulletin of the American Mathematical Society|doi=10.1090/S0273-0979-1979-14606-8|access-date=2021-02-04}}</ref> 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.<ref>{{Ref-llibre|cognom=Rota|nom=Gian Carlo|url=https://link.springer.com/book/10.1007/978-0-8176-4775-9|títol=Discrete Thoughts|data=1969|editorial=Birkhaüser|isbn=978-0-8176-4775-9|pàgines=50|doi=10.1007/978-0-8176-4775-9}}</ref> 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, [[Conjunt numerable|comptable]]) però [[Matemàtica discreta|discret]].
[[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» <ref>{{Citation|title=Book Review|url=https://www.ams.org/journals/bull/1979-01-02/S0273-0979-1979-14606-8/S0273-0979-1979-14606-8.pdf|journal=Bulletin of the American Mathematical Society|doi=10.1090/S0273-0979-1979-14606-8|access-date=2021-02-04}}</ref> 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.<ref>{{Ref-llibre|cognom=Rota|nom=Gian Carlo|url=https://link.springer.com/book/10.1007/978-0-8176-4775-9|títol=Discrete Thoughts|data=1969|editorial=Birkhaüser|isbn=978-0-8176-4775-9|pàgines=50|doi=10.1007/978-0-8176-4775-9}}</ref> 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, [[Conjunt numerable|comptable]]) però [[Matemàtica discreta|discret]].

== Història ==
[[Fitxer:Plain-bob-minor_2.png|dreta|miniatura|234x234px| 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 [[Edat antiga|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 <sup>6</sup>&nbsp;−&nbsp;1 possibilitats. L'[[historiador]] [[Antiga Grècia|grec]] [[Plutarc de Queronea|Plutarc]] comenta una discussió entre [[Crisip]] (segle III aC) i [[Hiparc de Nicea|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.<ref>{{Ref-publicació|cognom=Acerbi|nom=F.|url=https://link.springer.com/article/10.1007/s00407-003-0067-0|publicació=Archive for History of Exact Sciences|any=2003|volum=57|exemplar=6|pàgines=465–502|doi=10.1007/s00407-003-0067-0|consulta=2021-03-12|dataarxiu=2022-01-23}}</ref><ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>{{Ref-publicació|doi=10.1080/00029890.1998.12004906|any=1998|cognom=Habsieger|nom=Laurent|cognom2=Kazarian|nom2=Maxim|cognom3=Lando|nom3=Sergei|publicació=The American Mathematical Monthly|volum=105|exemplar=5|pàgines=446}}</ref> Abans, a l'''Ostomaquion'', [[Arquimedes|Arquímedes]] (segle III aC) podria haver considerat el nombre de configuracions d'un trencaclosques de rajoles, <ref>{{Ref-publicació|cognom=Netz|nom=R.|cognom2=Acerbi|nom2=F.|cognom3=Wilson|nom3=N.|url=https://www.sciamvs.org/2004.html|publicació=Sciamvs|volum=5|pàgines=67–99|consulta=2021-03-12|dataarxiu=2021-04-16}}</ref> mentre que els interessos combinatoris possiblement estaven presents en les obres perdudes d' [[Apol·loni de Perge|Apol·loni]].<ref>{{Ref-publicació|cognom=Hogendijk|nom=Jan P.|data=1986|url=https://www.jstor.org/stable/41133783|publicació=Archive for History of Exact Sciences|volum=35|exemplar=3|pàgines=187–253|doi=10.1007/BF00357307|jstor=41133783|issn=0003-9519|consulta=2021-03-26|dataarxiu=2021-04-18}}</ref><ref>{{Ref-publicació|cognom=Huxley|nom=G.|data=1967|url=https://grbs.library.duke.edu/article/view/11131/4205|publicació=Greek, Roman, and Byzantine Studies|volum=8|exemplar=3|pàgines=203|consulta=2021-03-26|dataarxiu=2021-04-16}}</ref>

A l' [[Edat mitjana|Edat Mitjana]], la combinatòria es va continuar estudiant, en gran part fora de la civilització europea. El matemàtic [[Índia|indi]] [[Mahavira (matemàtic)|Mahāvīra]] (c. 850 ) va proporcionar fórmules per al nombre de [[Permutació|permutacions]] i combinacions,<ref>{{Ref-llibre|cognom=Puttaswamy|nom=Tumkur K.|capítol=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor=Selin|títol=Mathematics Across Cultures: The History of Non-Western Mathematics|editorial=Kluwer Academic Publishers|lloc=Netherlands|url=https://books.google.com/books?id=2hTyfurOH8AC|any=2000|isbn=978-1-4020-0260-1|pàgines=417 <!-- pages 409–422 -->}}</ref> i aquestes fórmules poden haver estat familiars als matemàtics indis des del segle VI d.C.<ref>{{Ref-publicació|cognom=Biggs|nom=Norman L.|any=1979|publicació=Historia Mathematica|volum=6|exemplar=2|pàgines=109–136|doi=10.1016/0315-0860(79)90074-0|dataaccés=free}}</ref> El [[Filosofia|filòsof]] i [[astrònom]] rabí [[Abraham ibn Ezra]] ( c. 1140 ) va establir la simetria dels [[Coeficient binomial|coeficients binomials]], mentre que una fórmula tancada va ser obtinguda més tard pel [[Talmud|talmudista]] i [[matemàtic]] [[Guersònides|Levi ben Gerson]] (més conegut com a Gersonides), l'any 1321.<ref>{{Citation|isbn=978-1-4832-1863-2|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|accessdate=2015-01-25}}. (Translation from 1967 Russian ed.)</ref> 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 Tartaglia|triangle de Pascal]]. Més tard, a l'Anglaterra medieval, la campanologia va proporcionar exemples del que ara es coneix com a [[Camí hamiltonià|cicles hamiltonians]] en certs [[Graf de Cayley|gràfics de Cayley]] sobre permutacions.<ref>{{Ref-publicació|doi=10.1080/00029890.1987.12000711|any=1987|cognom=White|nom=Arthur T.|publicació=The American Mathematical Monthly|volum=94|exemplar=8|pàgines=721–746}}</ref><ref>{{Ref-publicació|doi=10.1080/00029890.1996.12004816|any=1996|cognom=White|nom=Arthur T.|publicació=The American Mathematical Monthly|volum=103|exemplar=9|pàgines=771–778}}</ref>

Durant el [[Renaixement]], juntament amb la resta de les matemàtiques i les [[Ciència|ciències]], la combinatòria va gaudir d'un renaixement. Les obres de [[Blaise Pascal|Pascal]], [[Isaac Newton|Newton]], [[Jakob Bernoulli|Jacob Bernoulli]] i [[Leonhard Euler|Euler]] esdevenen fonamentals en el camp emergent. En temps més moderns, els treballs de [[James Joseph Sylvester|JJ Sylvester]] (finals del segle XIX) i [[Percy Alexander MacMahon|Percy MacMahon]] (inicis del segle XX) van ajudar a establir les bases de la combinatòria enumerativa i algebraica. La [[Teoria de grafs|teoria dels grafs]] també va gaudir d'un creixent interès al mateix temps, especialment en relació amb el [[Teorema dels quatre colors|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.<ref>See [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory] {{Webarchive|url=https://web.archive.org/web/20210217150357/http://www.math.iit.edu/~kaul/Journals.html#CGT|date=2021-02-17}}</ref> 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 de nombres|teoria dels nombres]], etc. i que al mateix temps va provocar una fragmentació parcial del camp.


== Permutacions de subconjunts (r-permutacions o variacions) ==
== Permutacions de subconjunts (r-permutacions o variacions) ==

Revisió del 19:00, 12 maig 2024

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ó

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

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)

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:[22]


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

Amb repeticions

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

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

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

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

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:[3]

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

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

Referències

  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.com/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].

Vegeu també

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Combinatòria
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Combinatòria&oldid=33487188»