Combinatòria

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 dóna 8,0658·1067.

Permutacions de subconjunts (r-permutacions o variacions)[modifica | modifica el codi]

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

Sense repeticions (r-permutació)[modifica | modifica el codi]

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[modifica | modifica el codi]

 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 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 dóna el total (4*4*4 = 43)

Permutacions[modifica | modifica el codi]

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 | modifica el codi]

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[modifica | modifica el codi]

P_n^{n_1,n_2,...n_n}=\frac{n!}{n_1!n_2!....n_n!}


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

Combinacions[modifica | modifica el codi]

Sense repeticions[modifica | modifica el codi]

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[modifica | modifica el codi]

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é[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Combinatòria Modifica l'enllaç a Wikidata