Given five types of coins (5 cent, 10 cent, 20 cent, 50 cent, 1 dollar), give a formula for the number of possible collections of n coins which contain no more than four coins of any one type.
I am currently trying to solve this problem using the inclusion-exclusion principle given in my textbook as:
$$\sum\limits_{S \subseteq [n]} {{{( - 1)}^{|s|}}|\bigcap\limits_{i \in s} {{A_i}|} } $$
I have let ${{A_i}}$ be the subset of collections of $n$ coins with more than 4 $i$ coins, were $i$ takes the value of one of the types of coins.
I am stuck on figuring out how to calculate the value for ${|\bigcap\limits_{i \in s} {{A_i}|} }$ or even really being able to represent ${{A_i}}$.
Any tips or hints on how to go about the problem would be appreciated.
Here is a suggestion on how to calculate $A_S$. $A_S$ is the set of all collections of $n$ coins that contain at least 5 coins of type $i$ for all $i \in S$.
Thus we can see that the number of elements in $A_S$ is equal to the number of ways to pick $n-5\vert S\vert$ items of 5 types. This is because for each $i \in S$ we already must have at least 5 coins of type $i$ in our collection. By the stars and bars method, we have that the size of $A_S$ is $\binom{n-5\vert S \vert +4}{4}$.
This should help you evaluate your above sum. I would also point out that your sum should be indexed by $S \subseteq [5]$ rather than $S \subseteq [n]$. Can you see why?
Also, since the size of $A_S$ depends only on the size of $S$, you can group together terms in your sum to just have a sum from 0 to 5.