3
$\begingroup$

I am trying assignments of an Institute in which I don't study and i could not think about this problem.

Problem is -> Determine the number of 10-combinations of multisets S= { 3.a, 4.b, 5.c}

I think the answer should be number of solutions of equation $ x_1+ x_2+x_3$ =10 such that $0\leq x_1\leq 3 $ , $0 \leq x_2 \leq 4 $ , $ 0\leq x_3 \leq 5 $ .

But i am unable to think how to find solution of this equation under such constraints. Can somebody please help.

$\endgroup$
6
  • $\begingroup$ There is a section called Counting Multisets on the wiki page for Multiset. Or look at the wiki page for Combination under “with repetition”. Or look up Stars and Bars :) $\endgroup$
    – Milten
    Feb 17 '20 at 18:37
  • $\begingroup$ @Milten am I thinking in right direction? $\endgroup$
    – No -One
    Feb 17 '20 at 18:42
  • $\begingroup$ @Milten would the answer be 66? $\endgroup$
    – No -One
    Feb 17 '20 at 20:18
  • $\begingroup$ @Milten but the answer of Christian Blatter is 6? $\endgroup$
    – No -One
    Feb 17 '20 at 20:20
  • $\begingroup$ Oh, I am so sorry. I pointed you in the completely wrong direction. Yes, I agree with your strategy and that the answer is $6$. Those links only deal with unlimited repetition, which is not what we want. I did found a general solution here, but the formulas are not nice (the use inclusion-exclusion principle), so for small numbers I would probably just count the possibilities. $\endgroup$
    – Milten
    Feb 17 '20 at 20:35
4
$\begingroup$

I'm interpreting the problem in the sense indicated in the sentence "I think the answer should be $\ldots$".

As $0\leq x_3\leq5$ we must have $x_1+x_2\geq5$. Draw a figure of the $(x_1,x_2)$-plane, and you shall immediately see that there are exactly $6$ lattice points in the $[0,3]\times[0,4]$ rectangle satisfying this condition, namely $(1,4)$, $(2,3)$, $(2,4)$, $(3,2)$, $(3,3)$, and $(3,4)$. Since $(x_1,x_2)$ determines $x_3$ via $x_3=10-(x_1+x_2)$ it follows that the given problem has $6$ admissible solutions $(x_1,x_2,x_3)$.

$\endgroup$
3
  • $\begingroup$ but is this method right for such type of problem? $\endgroup$
    – No -One
    Feb 17 '20 at 19:44
  • $\begingroup$ Do you think $6$ is wrong? – The data appearing in your question are so small that this case analysis solution is most efficient. And it tells you how to solve such problems (with three variables, maybe more) when larger data are given. $\endgroup$ Feb 17 '20 at 19:49
  • $\begingroup$ I am not saying six is wrong. I am just asking whether for number of 10-combinations of multiset my method is right or wrong? Obviously if my method is right then 6 is correct answer. Actually I am taught this course by a really terrible teacher. So, was asking if my thinking is right for this case here. $\endgroup$
    – No -One
    Feb 17 '20 at 19:59
2
$\begingroup$

[EDIT: Btw, your interpretation as ways to sum to $10$ is completely correct :)]

I will just give two (and a half) other ways to work it out.

Since $|S|=12$ and we want to count $10$-combinations, it is simpler to count $2$-combinations instead (i.e. choose the elements not to go in the $10$-combination). There are $6$ of these: $$ \{a,a\}, \{b,b\}, \{c,c\}, \{a,b\}, \{a,c\}, \{b, c\} $$ These can be counted systematically by noting that we must choose either two of the same or two distinct elements, and then use basic combinatorics.

We can also note that $a,b,c$ all have multiplicity $\ge2$ in $S$. So the $2$-combinations of $S$ are the same as the $2$-combinations of the set $\{a,b,c\}$ with unlimited repetition. By stars and bars, that is $\binom{2+3-1}{2}=6$.

If we want to use a direct formula, we have to deal with a bunch of cases through inclusion-exclusion. With this method (as seen here), we get: $$ \binom{10+3-1}{2} - \Bigg[ \binom{6+3-1}{2} + \binom{5+3-1}{2} + \binom{4+3-1}{2} \Bigg] \\ + \Bigg[ \binom{1+3-1}{2} + \binom{0+3-1}{2} + 0 \Bigg] - 0 = 6 $$ (If you follow the link, note that the $56$ in their example should be $\binom{8}{2}=28$, and the correct answer is $9$).

$\endgroup$
1
  • 1
    $\begingroup$ thanks a lot for such a nice explanation $\endgroup$
    – No -One
    Feb 18 '20 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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