2
$\begingroup$

I have competition exam soon, and I need to have fast trick to answer the following:

What is the number of ways that I can select subset (k) from larger set (n) where the order is important and without replacement (I can't use the element more than once).

For example I have the set A={1,2,2} and I need to select only two number from the set. How many possibility are there?

will, manually its {(1,2),(2,1),(2,2)} so the answer is 3. How to get three directly without listing the possibilities???

Second thing, what if I have the same example but with replacement (I can use the element more than once)>>>> the answer is {(1,1),(1,2),(2,1),(2,2)}, so 4 possibilities, How to get 4 directly ??

$\endgroup$

1 Answer 1

1
$\begingroup$

With just two colours with multiplicities $m_1$ and $m_2$ we have the formula

$$ \sum_{i = \max\{0, k - m_2\}}^{\min\{m_1, k\}} \binom{k}{i} $$

which tells us to take a $k$-tuple and choose an $i$-element subset of the components and set them all to be $1$. This is only possible if $i_1 \le m_1$ because otherwise we just don't have enough $i_1$'s and similarly $i_2 = k - i_1 \le m_2$. This gives you the upper and lower limits.

With $(m_1, m_2, k) = (1, 2, 2)$ we have

$$ \sum_{i = 0}^{1} \binom{2}{i} = 1 + 2 = 3. $$

Another, somewhat more interesting example: $(m_1, m_2, k) = (3, 3, 4)$ gives us

$$ \sum_{i = 1}^{3} \binom{4}{i} = 4 + 6 + 4 = 14. $$


With $n$ colours and multiplicities $m_1, \dots, m_n$ you are looking at the sum

$$ \sum_{i_1,\dots,i_n} \binom{k}{i_1} \binom{k - i_1}{i_2} \cdots \binom{k - (i_1 + \dots + i_{n - 1})}{i_n} $$

over all tuples $(i_1,\dots,i_n)$ which satisfy $i_1 + \dots + i_n = k$ and $0 \le i_j \le m_j$ for $j = 1,\dots,n$.


For example with $\color{blue}{m_1 = 2}, \color{red}{m_2 = 4}, \color{purple}{m_3 = 6}$ and $k = 7$ we are looking at

\begin{align} \color{blue}{0} + \color{red}{1} + \color{purple}{6} &: \binom70 \binom71 \binom66 = 7 \\ \color{blue}{0} + \color{red}{2} + \color{purple}{5} &: \binom70 \binom72 \binom55 = 21 \\ \color{blue}{0} + \color{red}{3} + \color{purple}{4} &: \binom70 \binom73 \binom44 = 45 \\ \color{blue}{0} + \color{red}{4} + \color{purple}{3} &: \binom70 \binom74 \binom33 = 45 \\ \hline \color{blue}{1} + \color{red}{0} + \color{purple}{6} &: \binom71 \binom60 \binom66 = 7 \\ \color{blue}{1} + \color{red}{1} + \color{purple}{5} &: \binom71 \binom61 \binom55 = 42 \\ \color{blue}{1} + \color{red}{2} + \color{purple}{4} &: \binom71 \binom62 \binom44 = 105 \\ \color{blue}{1} + \color{red}{3} + \color{purple}{3} &: \binom71 \binom63 \binom33 = 140 \\ \color{blue}{1} + \color{red}{4} + \color{purple}{2} &: \binom71 \binom64 \binom22 = 105 \\ \hline \color{blue}{2} + \color{red}{0} + \color{purple}{5} &: \binom72 \binom50 \binom55 = 21 \\ \color{blue}{2} + \color{red}{1} + \color{purple}{4} &: \binom72 \binom51 \binom44 = 105 \\ \color{blue}{2} + \color{red}{2} + \color{purple}{3} &: \binom72 \binom52 \binom33 = 210 \\ \color{blue}{2} + \color{red}{3} + \color{purple}{2} &: \binom72 \binom53 \binom22 = 210 \\ \color{blue}{2} + \color{red}{4} + \color{purple}{1} &: \binom72 \binom54 \binom11 = 105 \\ \end{align}

for a total of $1171$.


If you allow replacement, the multiplicities do not matter and you just have $n^k$ where $n$ is the number of colours.

$\endgroup$
7
  • $\begingroup$ Can you please give example on the case of "With n colours and multiplicities m1,…,mn". Lets say I have 2*Blue (B), 4*Red (R) and 6*Green (G). And I need to select 7 marbles without replacement with order is important. How to do it ? $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 22:09
  • $\begingroup$ @LoveEva Done. You can do it a bit faster by noting that $$\sum_{k = 0}^n \binom{n}k = 2^n$$ For instance $$\binom50 + \binom51 + \dots + \binom54 = 2^5 - \binom55 = 2^5 - 1.$$ $\endgroup$
    – Sera Gunn
    Commented Jul 13, 2017 at 22:31
  • $\begingroup$ Can you just show how did you calculate i1, i2 and i3? @T.Gunn $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 22:50
  • $\begingroup$ is it all the possible ways of getting 7 from 3 numbers right ? $\endgroup$
    – Love Eva
    Commented Jul 13, 2017 at 22:55
  • $\begingroup$ @LoveEva For example in $\color{blue}{2} + \color{red}{1} + \color{purple}{4}$ you have $\color{blue}{i_1 = 2}, \color{red}{i_2 = 1}$ and $\color{purple}{i_4 = 4}$. Each number has to be less than the corresponding multiplicity and they must all sum to $k$. $\endgroup$
    – Sera Gunn
    Commented Jul 13, 2017 at 22:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .