profesional

Combinaciones con repeticiLon
En una heladerL.a disponen de 5 sabores diferentes para un helado. .De
cuLantas formas se pueden elegir 10 helados? En este ejemplo, se trata de
combinaciones (noimporta el orden de elecciLon) pero es obvio que hemos de
repetir sabor ya que n (5) es menor que r (10).
Sea A = {a1, a2, . . . , an} un conjunto finito de n elementos y sea r un
nLumeronatural. Una combinaciLon con repeticiLon de los n elementos de
A de orden r es una selecciLon no ordenada de r elementos, no necesariamente
distintos, de A.
Dos combinaciones con repeticiLon de ordenr son distintas si el nLumero
de apariciones de algLun elemento de A en las selecciones es diferente. Por
ejemplo, si A = {1, 2, 3, 4} son combinaciones con repeticiLon de orden tres
diferentes{1, 2, 3} y {1, 2, 4}, {1, 2, 2} y {1, 1, 2}. Sin embargo, son la misma
combinaciLon {1, 2, 3} y {1, 3, 2}, al igual que {2, 1, 2} y {2, 2, 1}.
Teorema 14. El nLumero de combinaciones conrepeticiLon de un conjunto de
n elementos de orden r es
CR(n, r) = C(n + r . 1, r) =

n + r . 1
r
!
=

n + r . 1
n . 1
!
.
Matematica Discreta. Area de Algebra
Universidade da Coruna
104CAPL ITULO 4. COMBINATORIA
DemostraciLon. Cada combinaciLon con repeticiLon de orden r de los elementos
de A se corresponde con una soluciLon de
x1 + x2 + . . . + xn = r,
siendo xi el nLumerode veces que elegimos el elemento i-Lesimo. AsL. pues,
estamos considerando Lunicamente soluciones (x1, x2, . . . , xn) con xi ¸ Z, xi .
0, para cada i. Por otro lado, cada soluciLon nonegativa (x1, x2, . . . , xn) de
la ecuaciLon anterior se corresponde con una cadena de r 1fs y n . 1 barras
distribuidos como:
x1 z }| {
1 . . . 1 |
x2 z }| {
1 . . . 1 | E E E |
xn z }| {
1 .. . 1
Por lo tanto, buscamos el nLumero de formas de colocar n.1 barras en n+r.1
posiciones2. Ese nLumero es claramente

n+r.1
n.1

=

n+r.1
r

.
Ejemplo 88. En una gran cesta de...