Combinations

Here is the problem: Sam and Tim direct Kim to the donut shop to keep her promise that she was buying them a dozendonuts due to a bet she lost. They said they liked glazed, maple, chocolate, or cake. She had to buy at least one of each and no more than 4 of any one kind. How many different way can Kim meet their demand?

I did a combination with repetition. 16!/(12!4!) = 1820 However, I know that I am not done with this problem and am stuck. I am not sure if I am using the correct formula either. Please help.

I think your solution may be too high.

We can do this various ways. i.e. generating functions or Inclusion-Exclusion Principle.

Using G.F.

There are 12 donuts of 4 types. There must be at least one of each type and no more than 4 of any one type.

Since there has to be at least one of each, place one of each in the box. Now, we have 8 donuts to place.

After the one of each is placed, there can be 0 to 3 of each type placed in the other 8 places.

This is the same as asking how many integer solutions there are to the equation:

\(\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=8, \;\ 0\leq x_{i}\leq 3\)

This gives:

\(\displaystyle \left(1+x+x^{2}+x^{3}\right)^{4}\)

Now, look at the coefficient of \(\displaystyle x^{8}\) in the expansion.

It is \(\displaystyle \boxed{31}x^{8}\)

The Inclusion-Exclusion Principle would involve \(\displaystyle \binom{11}{8}-4\cdot\binom{7}{4}+\binom{4}{2}\)

komark said:

Here is the problem: Sam and Tim direct Kim to the donut shop to keep her promise that she was buying them a dozendonuts due to a bet she lost. They said they liked glazed, maple, chocolate, or cake. She had to buy at least one of each and no more than 4 of any one kind. How many different way can Kim meet their demand?

Click to expand...

In the above solution note that the condition that at least one of each kind is not considered.
We need to find the coefficient of \(\displaystyle x^{12}\) in the expansion of \(\displaystyle \left( {\sum\limits_{k = 1}^4 {x^k } } \right)^4\).

Thanks for the heads up, pka. I immediately saw my mistake and fixed it.