Ok, so I am working on a combinatorics problem involving combination with repetition. The problem comes off a past test that was put up for study. Here it is:

An ice cream parlor sells six flavors of ice cream: vanilla, chocolate, strawberry, cookies and cream, mint chocolate chip, and chocolate chip cookie dough. How many combinations of fewer than 20 scoops are there? (Note: two combinations count as distinct if they differ in the number of scoops of at least one flavor of ice cream.)

Now I get the correct answer $\binom{25}{6}$, but the way they arrive at the answer is different and apparently important. I just plug in 20 combinations of 6 flavors into $\binom{n+r-1}{r}=\binom{n+r-1}{n-1}$. The answer given makes use of a "null flavor" to be used in the calculation. I can't figure out for the life of me why, could someone explain this to me?


This is a slight variation on the standard combinations with repetition problem. The difference here is that we are not trying to buy exactly 19 scoops of ice cream, but 19 or fewer scoops. We can solve this problem by introducing a 7 th flavor, called “noflavor” ice cream. Now, imagine trying to buy exactly 19 scoops of ice cream from the 7 possible flavors (the six listed an “no-flavor”). Any combination with only 10 real scoops would be assigned 9 “no-flavor” scoops, for example. There is a one-to-one correspondence between each possible combination with 19 or fewer scoops from 6 flavors as there are to 19 “scoops” from 7 flavors. Thus, using the formula for combination with repetition with 19 items from 7 types, we find the number of ways to buy the scoops is $\binom{19+7-1}{19}=\binom{25}{19}=\binom{25}{6}$. (Grading – 4 pts for mentioning the idea of an extra flavor, 4 pts for attempting to apply the correct formula, 2 pts for getting the correct answer. If a sum is given instead of a closed form, give 6 points out of 10.)

Any assistance would be greatly appreciated!


Suppose that the problem had asked how many combinations there are with exactly $19$ scoops. That would be a bog-standard problem involving combinations with possible repetition (sometimes called a stars-and-bars or marbles-and-boxes problem). Then you’d have been trying to distribute $19$ scoops of ice cream amongst $6$ flavors, and you’d have known that the answer was $\binom{19+6-1}{6-1}=\binom{24}{5}$, either by the usual stars-and-bars analysis or simply by having learnt the formula. Unfortunately, the problem actually asks for the number of combinations with at most $19$ scoops. There are at least two ways to proceed.

The straightforward but slightly ugly one is to add up the number of combinations with $19$ scoops, $18$ scoops, $17$ scoops, and so on down to no scoops at all. You know that the number of combinations with $n$ scoops is $\binom{n+6-1}{6-1}=\binom{n+5}{5}$, so the answer to the problem is $\sum\limits_{n=0}^{19}\binom{n+5}{5}$. This can be rewritten as $\sum\limits_{k=5}^{24}\binom{k}{5}$, and you can then use a standard identity (sometimes called a hockey stick identity) to reduce this to $\binom{25}{6}$.

The slicker alternative is the one used in the solution that you quoted. Pretend that there are actually seven flavors: let’s imagine that in addition to vanilla, chocolate, strawberry, cookies and cream, mint chocolate chip, and chocolate chip cookie dough there is banana. (The quoted solution uses ‘no-flavor’ instead of banana.) Given a combination of exactly $19$ scoops chosen from these seven flavors, you can throw away all of the banana scoops; what remains will be a combination of at most $19$ scoops from the original six flavors. Conversely, if you start with any combination of at most $19$ scoops of the original six flavors, you can ‘pad it out’ to exactly $19$ scoops by adding enough scoops of banana ice cream to make up the difference. (E.g., if you start with $10$ scoops of vanilla and $5$ of strawberry, you’re $4$ scoops short of $19$, so you add $4$ scoops of banana.) This establishes a one-to-one correspondence (bijection) between (1) the set of combinations of exactly $19$ scoops chosen from the seven flavors and (2) the set of combinations of at most $19$ scoops chosen from the original six flavors. Thus, these two sets of combinations are the same size, and counting one is as good as counting the other. But counting the number of combinations of exactly $19$ scoops chosen from seven flavors is easy: that’s just the standard combinations with repetitions problem, and the answer is $\binom{19+7-1}{7-1}=\binom{25}{6}$.

Both solutions are perfectly fine; the second is a little slicker and requires less computation, but the first is also pretty straightforward if you know your basic binomial identities.


Without using a null, the 'standard calculation' is very annoying. The standard idea would be to see how many ways no scoops can be taken, plss how many ways 1 can be taken, plus 2, ... plus 19. Using a null simplifies all that to one step, as having 1 null just means that you are looking at 18 scoops. 2 nulls means 17 scoops, etc.

It's more troublesome that you just took ${ n + r - 1 \choose n - 1}$.With 20 and 6, you are literally saying how many ways exactly 20 scoops can be chosen from 6 flavors, which is not at all what the question asks. But perhaps you already considered combinatorial identities?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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