# How many possible ways are there?

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?

• Is there a computer science motivation/relation to this question? If not, this question belongs to math.SE. – Raphael Apr 22 '12 at 17:06
• 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. – Gilles 'SO- stop being evil' Apr 22 '12 at 17:28
• – Raphael Apr 23 '12 at 7:00

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$$
• 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. – Raphael Apr 22 '12 at 21:42