Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.