Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

4 Answers 4

up vote 2 down vote accepted

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$

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.