# 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.

-

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$$

-
Right - but how do you find all the solutions of that? That is the question here. –  Electro May 22 '12 at 20:09
In general problem is not easy to solve. On can use generating functions and in some particular cases we can find interesting solutions. –  Adi Dani May 22 '12 at 20:50