# Probability with order and without/with replacement for repeated elements

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 ??

## 1 Answer

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.

• 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 ? Commented Jul 13, 2017 at 22:09
• @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.$$ Commented Jul 13, 2017 at 22:31
• Can you just show how did you calculate i1, i2 and i3? @T.Gunn Commented Jul 13, 2017 at 22:50
• is it all the possible ways of getting 7 from 3 numbers right ? Commented Jul 13, 2017 at 22:55
• @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$. Commented Jul 13, 2017 at 22:59
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/2357787/probability-with-order-and-without-with-replacement-for-repeated-elements", "fetch_time": 1721557834000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-30/segments/1720763517663.24/warc/CC-MAIN-20240721091006-20240721121006-00544.warc.gz", "warc_record_offset": 332398646, "warc_record_length": 36881, "token_count": 1629, "char_count": 4306, "score": 4.4375, "int_score": 4, "crawl": "CC-MAIN-2024-30", "snapshot_type": "latest", "language": "en", "language_score": 0.832791268825531, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00019-of-00064.parquet"}