I have been struggling with this combinatorial problem (inspired from a competitive programming problem). The statement is:
John wants to eat a piece of fruit every day for the next $N$ days. More precisely, every day, he will eat exactly one of the following: an apple, an orange, a banana or a rambutan.
He believes that a healthy nutrition is based on variety, so among the $N$ pieces of fruit he will eat, there need to be:
at least $A$ apples
at least $B$ bananas
at least $O$ oranges
at least $R$ rambutan
He wonders how many different meal plans exist that will satisfy those criteria. Two meal plans are different if there exists an integer $i$ with $1 \leq i \leq N$ such that the two meal plans prescribe a different piece of fruit on the $i$-th day.
So far I could only come up with the following solution (which over counts try it with $N$ = 3, $O$ = 2, the rest being zero):
$$Answer =\binom{N}{R} \cdot \binom{N - R}{ O} \cdot \binom{N - R - O}{A} \cdot \binom{N - R - O - A}{B} \cdot 4^K $$ where $k = N - (R+A+O+B)$
however this gives 12 instead of 10 for the mentioned test case.
The reason that you're over-counting is that you are making some fruits special. For example, you've specified $A$ of the apples to be special by placing them down first, but the $4^k$ term may also contain apples.
To fix this, you need to case on exactly how many of each fruit there are. First, we can realize that if, say, $n_A$ apples are included, $n_B$ bananas, etc., then $n_A+n_B+n_O+n_R=N$ and the total number of meal plans using these numbers is $$ {N\choose n_A,n_B,n_O,n_R}={N\choose n_A}{N-n_A\choose n_B}{N-n_A-n_B\choose n_O}{N-n_A-n_B-n_O\choose n_R}. $$ Now, since $n_A\geq A$, etc., we can compute the total number of meal plans through the sum $$ \sum_{k_A+k_B+k_O+k_R=k:\ k_*\geq 0}{N\choose A+k_A,B+k_B,O+k_O,R+k_R}, $$ where $k=N-(A+B+O+R)$.