Combinacions amb repetició

Les combinacions amb repetició de $n$ elements presos de $k$ en $k$ són els diferents grups de $k$ elements que es poden formar a partir d'aquests $n$ elements, permetent que els elements es repeteixin, i considerant que dos grups es diferencien només si tenen elements diferents ( és a dir, no importa l'ordre). Es representen per $C R_{n, k}$ .

Exemple

Considerem el conjunt $A = {a, b, c, d, e}$ , les diferents combinacions amb repetició d'aquests $5$ elements són:

Combinacions amb repetició de $5$ elements presos de $1$ en $1$ : $a$ , $b$ , $c$ , $d$ i $e$ .
Combinacions amb repetició de $5$ elements presos de $2$ en $2$ : Com abans, es tenen $a d$ , $a b$ , $a c$ , $a e$ , $b c$ , $b d$ , $b e$ , $c d$ , $c e$ i $d e$ , però ara també es tenen els grups amb elements repetits: $a a$ , $b b$ , $c c$ , $d d$ i $e e$ .
Combinacions amb repetició de 5 elements presos de $3$ en $3$ : Com abans, tenim $a b e$ , $a b c$ , $a b d$ , $a c d$ , $a c e$ , $a d e$ , $b c d$ , $b c e$ , $b d e$ and $c d e$ , però ara també es tenen els grups amb elements repetits: $a a b$ , $a a c$ , $a a d$ , $a a e$ , $b b a$ , $b b c$ , $b b d$ , $b b e$ , $c c a$ , $c c b$ , $c c d$ , $c c e$ , $d d a$ , $d d b$ , $d d c$ i $d d e$ .
Combinacions amb repetició de $5$ elements presos de $4$ en $4$ : Com abans, tenim $a b c d$ , $a b c e$ , $a b d e$ , $a c d e$ i $b c d e$ , però ara també es tenen els grups amb elements repetits: $a a a b$ , $a a a c$ , $a a a d$ , $a a a e$ , $a a b c$ , $a a b d$ , $a a b e$ , $a a c d$ , $a a d e$ , $b b b a$ , $b b b c$ , etc...
Combinacions amb repetició de $5$ elements presos de $5$ en $5$ : A part del que ja teníem abans (que era $a b c d e$ ) ara també es tenen els grups amb elements repetits: $a a a a a$ , $a a a a b$ , $a a a a c$ , $a a a a d$ , $a a a a e$ , $a a a b c$ , $a a a b d$ , $a a a b e$ , $a a a c d$ , $a a a c e$ , $a a a d e$ , etc...

Com es pot veure en aquest exemple, ara hi ha molts més grups possibles que abans. La següent fórmula ens diu quantes combinacions amb repetició de $n$ elements presos de $k$ en $k$ hi ha:

$C R_{n, k} = (\binom{n + k - 1}{k}) = \frac{(n + k - 1)!}{(n - 1)! k!}$

En l'exemple anterior,

Exemple

Si es vol saber quantes combinacions amb repetició de $5$ elements presos de $3$ en $3$ hi ha, utilitzant la fórmula s'obté que són $35$ :

$C R_{5, 3} = (\binom{5 + 3 - 1}{3}) = \frac{(5 + 3 - 1)!}{(5 - 1)! 3!} = \frac{7!}{4! 3!} = 7 \cdot 5 = 35$