# I have n flavors of icecream. I choose k scoops, where k can be larger or smaller than n. How to generate all possible sequences?

Say I have 4 flavors of icecream, a, b, c, and d, and I want to get 3 scoops.

So basically I want to generate all possible 4-tuples where the sum of all elements in each tuple adds up to 3, like:

(3, 0, 0, 0) (0, 3, 0, 0) (0, 0, 3, 0) (0, 0, 0, 3) (2, 1, 0, 0) (2, 0, 1, 0) ... and so on, so that to generate all possible 3-scoop outcomes that can exist in menu of 4 flavors.

So for example the 5th 4-tuple I typed above would translate into an item that has 2 scoops of flavor a, 1 scoop of flavor b, no scoops of flavor c and no scoops of flavor d.

Is there a nice way of counting these things and generating them, for all cases where flavors=scoops, flavors>scoops and scoops>flavors...?

Thank you all in advance!

-
What kind of answer are you looking for? If you allow a recursive description in terms of $k$ and $n$, there are obvious solutions. For instance when $n>0$, recursively solve for $n-1$ and all $k'\leq k$; then for each solution complete with $k-k'$ scoops of flavor $n$. – Marc van Leeuwen Jul 12 '12 at 14:16
Basically, I'm trying to figure out how powers of terms of polynomials of n-th degree work out. If you have (a+b+c+d)^f, I can find the coefficient for each term using the multinomial theorem but first I need to know the partition of f as powers across a, b, c, and d. I hope what I'm thinking makes sense, I'm not really good at math :~| – Foivos Jul 12 '12 at 14:19

## 4 Answers

Let $x_1,x_2,x_3,x_4$ denotes the number of scoops of different flavors,then since the total number of scoops $=3$$\implies 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\choose 4-1}={6\choose 3}=20$- This is the most elegant answer. Thank you sir! – Foivos Jul 12 '12 at 17:39 No need to mention :):) – Aang Jul 13 '12 at 5:58 I think you need to use the counting formula for a multiset of size$k=3$chosen from$n=4$distinct species. The number of such multisets is $$\left(\left(\begin{array}{c}n \\ k \end{array}\right)\right) = \left(\begin{array}{c} n+k-1\\ k \end{array}\right).$$ The same formula arises in counting the number of monomials of degree$k$constructed from$n$variables$x_1,\dots x_n$, and in lots of other situations. - When repetition in the selection of the objects are allowed , the number of ways of selecting$r$objects from$n$distinct objects is$C(n+r-1,r)$. In your case you have 4 distinct flavors and you have to select$3$scoops in which flavors can be repeated. - Assume the flavors are numbered from$1$to$n$, starting with all$k$scoops of flavor$1$, the following procedure will advance through all$\binom{n-1+k}k$possibilities until reaching the choice of all$k$scoops of flavor$n$. Repeat: find the first flavor$i$with currently at least one scoop chosen; as long as$i<n$, replace one of those scoops by a scoop of flavor$i+1$, and all others (of flavor$i$) by scoops of flavor$1$(the latter step does nothing if$i=1$). This generates all$n$tuples of sum$k\$ in right-to-left lexicographic order.

-