Combinaciones con repetición

El número de estas selecciones es \(\binom{n+k-1}{k}\). Para verlo, se representa cada selección con \(k\) estrellas y \(n-1\) barras que separan los tipos. Por ejemplo, con 3 tipos y 5 objetos, \(\star\star|\star|\star\star\) significa 2 del primero, 1 del segundo y 2 del tercero. Cada selección es una fila de \(k+n-1\) símbolos en la que se eligen las \(k\) posiciones de las estrellas, y eso da \(\binom{n+k-1}{k}\).

El mismo conteo resuelve ecuaciones: las soluciones enteras no negativas de \(x_1+\dots+x_n=k\) son las selecciones de \(k\) objetos de \(n\) tipos, donde \(x_i\) cuenta cuántos hay del tipo \(i\). Si hay cotas inferiores, se resta primero: con \(x_i\ge 1\) se sustituye \(y_i=x_i-1\) y quedan \(k-n\) unidades por repartir. Si la condición es una desigualdad \(\le\), se añade una variable de holgura.

Conviene distinguirlo de los otros conteos: con orden y con repetición hay \(n^k\); con orden y sin repetición, \(n!/(n-k)!\); sin orden y sin repetición, \(\binom{n}{k}\); y sin orden y con repetición, \(\binom{n+k-1}{k}\). Error típico: usar \(\binom{n}{k}\) cuando se pueden repetir elementos, o \(n^k\) cuando el orden no importa.