Proof using double counting to show equality

Question

How to prove using double counting that the number of ways of choosing 5 elements from 4 types is equal to the number of ways of choosing 3 elements from 6 types.

I see that this is the case but don't know how to formally prove this using double counting. Could someone give an idea?

Answer 1

You want to count the number of nonnegative integer solutions to two equations: \begin{align} x_1 + x_2 + x_3 + x_4 &= 5\\ y_1 + y_2 + y_3 + y_4 + y_5 + y_6 &= 3 \end{align}

Apply stars and bars, and interchange the roles of stars and bars: $$\binom{5+4-1}{4-1}=\binom{8}{3}=\binom{8}{5}=\binom{3+6-1}{6-1}$$