Finding number of combinations for similar items

Question

I have 4 types of popsicle colors: Red, white, yellow, green. In the grocery store, there's 11 popsicles of each type, all together 44 popsicles. I need to find the number of combinations for choosing 26 of them. No restrictions on the order of choosing, same types are consider the same. I need to use either Inclusion–exclusion principle or Generating function.

Thanks a lot

Answer 1

Using the "dots and lines" approach, the number of solutions in non-negative integers of the equation $$x_1+x_2+x_3+x_4=26\tag{$*$}$$ is $C(29,3)$. However, your problem is more complicated because we also have the condition that $x_1,x_2,x_3,x_4\le11$. We shall count the number of solutions by PIE (the principle of inclusion/exclusion).

Let $\cal U$ be the set of all solutions of $(*)$, and for $k=1,2,3,4$, let $A_k$ be the set of all solutions in which $x_k\ge12$. Then the set of solutions that we wish to count is $$\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}\cap\overline{A_4}\ .$$ By PIE, the number we want is $$\eqalign{|{\cal U}|{}-|A_1\cup A_2\cup A_3\cup A_4| &=|{\cal U}|-|A_1|-\cdots+|A_1\cap A_2|+\cdots\cr &\qquad{}-|A_1\cap A_2\cap A_3|-\cdots+|A_1\cap A_2\cap A_3\cap A_4|\ .\cr}$$ To count $A_1$ we put $12$ dots aside, distribute the remainder over $4$ categories in $C(17,3)$ ways, then add the $12$ back to $x_1$ inorder to guarantee that $x_1\ge12$. Similarly, to count $A_1\cap A_2$ we put aside $24$ dots, arrange the remaining $2$ in $C(5,2)$ ways, and add $12$ each back to $x_1$ and $x_2$. Doing the rest similarly and noting that the later terms are zero gives the answer $$C(29,3)-4C(17,3)+6C(5,3)\ .$$

Comments.

• "Dots and lines" is also known as "stars and bars", especially in the USA for some reason ;-)
• Instead of "putting dots aside" you can make a substitution $y_k=x_k-12$. This works fine too, but IMHO the method I have given should help you to obtain an intuitive feel for the problem instead of just memorising techniques.