Tengo n sabores de helado. Elijo k bolas, donde k puede ser mayor o menor que n. ¿Cómo generar todas las secuencias posibles?

Question

Digamos que tengo 4 sabores de helado, a, b, c y d, y quiero tomar 3 bolas.

Así que básicamente quiero generar todas las posibles 4-tuplas donde la suma de todos los elementos en cada tupla sume 3, como:

(3, 0, 0, 0) (0, 3, 0, 0) (0, 0, 3, 0) (0, 0, 0, 3) (2, 1, 0, 0) (2, 0, 1, 0) ... y así sucesivamente, de modo que para generar todos los posibles resultados de 3 que pueden existir en el menú de 4 sabores.

Así, por ejemplo, la 5ª cuádruple que he escrito antes se traduciría en un artículo con 2 cucharadas del sabor a, 1 cucharada del sabor b, ninguna cucharada del sabor c y ninguna cucharada del sabor d.

¿Existe una forma agradable de contar estas cosas y generarlas, para todos los casos en los que sabores=cucharadas, sabores>cucharadas y cucharadas>sabores...?

Gracias a todos de antemano.

Answer 1

Creo que hay que utilizar la fórmula de recuento para un multiset de tamaño $k=3$ elegido entre $n=4$ especies distintas. El número de estos conjuntos múltiples es $$\left(\left(\begin{array}{c}n \\ k \end{array}\right)\right) = \left(\begin{array}{c} n+k-1\\ k \end{array}\right).$$ La misma fórmula surge al contar el número de monomios de grado $k$ construido a partir de $n$ variables $x_1,\dots x_n$ y en muchas otras situaciones .

Answer 2

Cuando se permite la repetición en la selección de los objetos , el número de formas de seleccionar $r$ objetos de $n$ objetos distintos es $C(n+r-1,r)$ .
En tu caso tienes 4 sabores distintos y tienes que seleccionar $3$ cucharadas en las que se pueden repetir los sabores.

Answer 3

Supongamos que los sabores están numerados de $1$ a $n$ empezando por todos $k$ cucharadas de sabor $1$ el siguiente procedimiento avanzará a través de todos los $\binom{n-1+k}k$ posibilidades hasta llegar a la elección de todas $k$ cucharadas de sabor $n$ . Repite: encuentra el primer sabor $i$ con actualmente al menos una primicia elegida; siempre y cuando $i<n$ sustituye una de esas cucharadas por una cucharada de sabor $i+1$ y todos los demás (de sabor $i$ ) por cucharadas de sabor $1$ (este último paso no hace nada si $i=1$ ). Esto genera todos los $n$ tuplas de suma $k$ en orden lexicográfico de derecha a izquierda.

Answer 4

Sea $x_1,x_2,x_3,x_4$ denota el número de cucharadas de diferentes sabores,entonces como el número total de cucharadas $=3$$$ \x_1+x_2+x_3+x_4=3 $$ where $ x_1,x_2,x_3,x_4\geq 0 $. The number of solutions of this equation $ ={3+4-1\ elegir 4-1}={6\ elegir 3}=20$