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.

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.

Vegeu també

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

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Combinatòria

• 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