Number of k-combinations of a multiset Say that I'm buying cakes for a party. I wish to buy $k$ cakes, and there are $n$ different kinds of cake, but only $m_i$ of each kind of cake (where $i$ denotes the $i$th kind). How many different combinations of cakes could I buy?
Context: I need to find the number of 4-character selections of "POSSESSES". Enumerating all of them gives me the expected result of 12, but I'd like a more... general solution for future reference.
 A: If we have $a_1$ objects of first kind $a_2$ objects of second kind ... $a_m$ objects of m-kind then choosing k-objects where $$0\leq k\leq a_1+a_2+...+a_m$$ is called a k-combination of multiset and the number of solutions of equation
$$r_1+r_2+...+r_m=k$$ where $0\leq r_i\leq a_i,i\in {1,2,...,m}$ gives the number of k-combinations of multiset. 
Multiset POSSESSES include
1 element P 
1 element O
5 elements S
2 elements E
so $a_1=1, a_2=1, a_3=5, a_4=2$ 
we needs to find the solutions of equation
$$r_1+r_2+r_3+r_4=4$$ where $$0\leq r_1\leq 1,0\leq r_2\leq 1,0\leq r_3\leq 5,0\leq r_4\leq 2 $$
A: I think I can get you most of the way towards a solution...
If you have a set $S$ = {P, O, E, E, S, S, S, S, S}, i.e. the letters of "POSSESSES", then you have $k$ = 4 distinct elements: {P, O, E, S}.
Let $X_T$ = {4-combinations in $T$}, the number of combinations of 4 elements in $T$, where $T$ is any set. Then we want to find a formula for $|X_S|$.
As explained here, if we had a set $S'$ where each of our $k$ distinct elements are repeated at least $r$ times in $S'$, then:
$|X_S'| = C(k + r - 1, r)$
(An example of such an $S'$ is $S'$ = {P, P, P, P, O, O, O, O, E, E, E, E, S, S, S, S}.)
$|X_S'| = C(k + r - 1, r) = C(4 + 4 - 1, 4) = C(7, 4) = 35$.
We can start with $|X_S'|$, which will certainly be larger than $|X_S|$, and start subtracting out all the elements in $X_S'$ that won't be in $X_S$ because they use too many letters. (In particular, {P, P, P, P} will have been counted, as will have {O, O, O, O}, {P, P, O, O}, {P, P, S, S}, etc.)
So let:

*

*$A_P$ = {4-combinations of $S'$ containing 2 or more occurrences of P}

*$A_O$ = {4-combinations of $S'$ containing 2 or more occurrences of O}

*$A_E$ = {4-combinations of $S'$ containing 3 or more occurrences of E}

(Noting that our set $S$ has more than $r=4$ repeats of the letter S, but not enough of P, O, or E.)
Then $|X_S|$, the number of 4-combinations in $S$ can be found by subtracting out all combinations of these events from the number of 4-combinations from $S'$:
$|X_S| = |X_S'| - (|A_P| + |A_O| + |A_E|) + (|A_P \cap A_O| + |A_P \cap A_E| + |A_O \cap A_E|) - |A_P \cap A_O \cap A_E|$
But $|X_S'| = C(k + r - 1, r) = C(4 + 4 - 1, 4) = C(7, 4) = 35$, and $|A_P \cap A_E| = |A_O \cap A_E| = |A_P \cap A_O \cap A_E| = 0$, so:
$|X_S| = 35 - |A_P| - |A_O| - |A_E| + |A_P \cap A_O|$
And $|A_P \cap A_O| = 1$ since $A_P \cap A_O$ = {P, P, O, O}, so:
$|X_S| = 36 - |A_P| - |A_O| - |A_E|$
Finally, $|A_P| = |A_O| = C(4+2-1, 2) = C(5, 2) = 10$, and $|A_E| = C(4, 1) = 4$:
$|X_S| = 36 - 10 - 10 - 4$
$|X_S| = 12$.
I've taken some shortcuts in the calculations, but I hope the idea makes sense. If not, try reading this.
