3
$\begingroup$

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!

  • 0
    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 :~|2012-07-12

4 Answers 4

2

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$

  • 0
    No need to mention :):)2012-07-13
2

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.

2

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.

2

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, 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.