1
$\begingroup$

Suppose I have the given data set of length 11 of scores:

p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1]

I want to select scores 6, 5, 5, 4, 2, 2 from the data set. How many ways are there?

For the above example answer is: 6 ways

{p[1], p[2], p[4], p[5], p[7], p[8]}
{p[10], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[10], p[5], p[7], p[8]}
{p[9], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[9], p[5], p[7], p[8]}
{p[10], p[2], p[9], p[5], p[7], p[8]}

How can I count the ways in general?

$\endgroup$
  • 1
    $\begingroup$ Is there a computer science motivation/relation to this question? If not, this question belongs to math.SE. $\endgroup$ – Raphael Apr 22 '12 at 17:06
  • $\begingroup$ Jack, @Raphael: a combinatorics formula would be a math question. I've reworded the question to ask for a counting method, which is more of a computer science question. $\endgroup$ – Gilles Apr 22 '12 at 17:28
  • $\begingroup$ Crossposted on math.SE. $\endgroup$ – Raphael Apr 23 '12 at 7:00
3
$\begingroup$

Say you want to pick, out of a multiset $S$, the numbers $x_1$, $x_2$, ..., $x_n$ with multiplicity $m_1$, $m_2$, ..., $m_n$ (i.e., you want to pick $x_1$ exactly $m_1$ times). Furthermore, assume that in $S$ the numbers $x_1$, $x_2$, ..., $x_n$ have multiplicity $s_1$, $s_2$,..., $s_n$. (we assume for every $i$, $s_i \ge m_i$, otherwise no solution exists).

Consider the first element $x_1$: you have exactly $s_1 \choose m_1$ different ways to pick $m_1$ occurrences of $x_1$ from the $s_1$ times it appears in $S$.

In a similar way for all the other elements, the answer would be $${s_1 \choose m_1} {s_2 \choose m_2} \cdots {s_n \choose m_n} = \prod_{i=1}^n {s_i \choose m_i}$$


For your example, set $x_1=6$, $x_2=5$, $x_3=4$, $x_4=2$. In the data set they appear with multiplicity $s_1=1$, $s_2=2$, $s_3=1$, $s_4=4$ and you want to have $m_1=1$ sixes, $m_2=2$ fivess, $m_3=1$ fours and $m_3=2$ twos, so the number of different options is $$ {1 \choose 1} {2 \choose 2} {1 \choose 1}{4 \choose 2} = 1 \cdot 1 \cdot 1 \cdot 6$$

$\endgroup$
  • $\begingroup$ Note that with the usual definition of the binomial coefficient, you don't need to assume $s_i \leq m_i$ as otherwise $\binom{s_i}{m_i} = 0$. Be aware, though; Mathematica (and possibly others) use a different generalisation. $\endgroup$ – Raphael Apr 22 '12 at 21:42

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.