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
$\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
    Jul 13 '17 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$ Jul 13 '17 at 22:31
  • $\begingroup$ Can you just show how did you calculate i1, i2 and i3? @T.Gunn $\endgroup$
    – Love Eva
    Jul 13 '17 at 22:50
  • $\begingroup$ is it all the possible ways of getting 7 from 3 numbers right ? $\endgroup$
    – Love Eva
    Jul 13 '17 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$ Jul 13 '17 at 22:59

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.