$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$

Probability - Counting

^{First created in September 2010}

Ordered Selections with Repetition: If $n$ distinct elements are to be arranged in order and repetition is allowed, there are $n$ possibilities to select an element for the first position, and also $n$ possibilities to select for the second position, and so on. Therefore, there are $n^n$ possible arrangements.

$\therefore\boxed{n^n=\text{Number of ordered arrangements of }n\text{ elements with repetition.}}$

If $r$ elements are to be arranged in order out of $n$ elements repetition allowed, there are $r$ positions to fill. Therefore, there are $n^r$ possible arrangements. (Note: $r\geq 0$; $r$ can be larger than $n$ .)

$\therefore\boxed{n^r=\text{Number of ordered arrangements of }r\text{ elements from a set of }n\text{ with repetition.}}$

Permutations

A permutation is an ordered arrangement of elements selected from a certain set without repetition.

If there are $n$ distinct elements in the set, there are $n$ possibilities to select an element for the first position. After that, as repetition is not allowed, there are only $n-1$ remaining elements to be selected for the second position. Likewise, there are $n-2$ elements for the third position, and so on. Therefore, there are $n(n-1)(n-2)\ldots 3\cdot 2\cdot 1$ possible permutations in total. This number is called "$n$ factorial" — $n!$.

Definition: $\boxed{n!=n(n-1)(n-2)\ldots 3\cdot 2\cdot 1=\text{Number of permutations selected from a set of }n\text{ elements.}}$

e.g. There are $5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$ permutations for 5 distinct elements.

If $r$ elements are selected out of a set of $n$ $(r\leq n)$, there are only $r$ positions to fill. Therefore, there are $n(n-1)\ldots(n-r+1)$ permutations, which equals to

$\displaystyle n(n-1)\ldots(n-r+1)\cdot\frac{(n-r)(n-r-1)\ldots 2\cdot 1}{(n-r)(n-r-1)\ldots 2\cdot 1} =\frac{n!}{(n-r)!} .$

Alternatively, if we line up all $n$ elements, we can put the first $r$ elements in one group and the last $n-r$ elements in another. There are still $n!$ permutations in total, but for each of the permutation of the first group or $r$, there are $(n-r)!$ permutations for the second group. These $(n-r)!$ permutations are in fact counted as one if only the first $r$ elements is of interest. That means the "total number of permutations" ($n!$)} is $(n-r)!$ times the "number of permutations of $r$ elements out of $n$" $(^nP_r)$. So $(n-r)!\cdot(^nP_r)=n!~$.

Definition: $\boxed{^nP_r=\frac{n!}{(n-r)!}=\text{Number of permutations of }r\text{ elements selected from a set of } n\text{ elements \it without \rm repetition.}}$

e.g. There are $^5P_3=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60$ permutations of 3 elements selected from a set of 5 elements.

Note: $\displaystyle \because n!=\:^nP_n=\frac{n!}{(n-n)!}=\frac{n!}{0!}\:,~\therefore 0!=\frac{n!}{n!}.\boxed{0!=1}$

Combinations

A combination is an unordered subset of elements selected from a certain set.

With reference to the analysis of permutations (ordered arrangements), since there are $^nP_r$ ways to arrange $r$ elements from a set of $n$, if their order is not of interest, for each selection of $r$ elements, the $r!$ permutations of them are in fact the same selection and therefore counted as one. So the "number of permutations" ($^nP_r$) is $r!$ times the "number of combinations" ($^nC_r$). So $r!\cdot(^nC_r)=\:^nP_r=\frac{n!}{(n-r)!}.$

Definition: $\boxed{^nC_r=\binom{n}{r}=\frac{n!}{r!(n-r)!} =\text{Number of combinations of }r\text{ elements selected from a set of }n\text{ elements.}}$

e.g. There are $^5C_3=\frac{5!}{3!(5-3)!}=\frac{5!}{3!2!}=10$ combinations of 3 elements selected from a set of 5 elements.

Note: $\displaystyle \because\:^nC_r=\frac{n!}{r!(n-r)!}=\frac{n!}{[n-(n-r)]!(n-r)!} =\:^nC_{n-r}\:,~\therefore\boxed{^nC_r=\:^nC_{n-r}}\:.$

i.e. There are as many ways to "include" $r$ elements from a set of $n$ as to "exclude" $n-r$ elements from it.

Groups

When some elements need to be together in the arrangement, each group is taken as one element, and the total number of permutations is $\boxed{n!\prod_{r=1}^n g_r!}$, where $n$ is the number of groups (individual elements are taken as groups of one), and $g_r$ is the number of elements in group $r$ (which might be 1).

e.g. Ways to arrange letters abcdefg with ab and def together: We have four groups — "ab", "c", "def" and "g". So $g_1=2, g_2=1, g_3=3, g_4=1$ and $n=4$ . There are $4!\times(2!\times 1!\times 3!\times 1!)=288$ ways.}\

Separation

When there are $r$ elements that need to be separated in the arrangement of $n$ ($r\leq n+1$), first place the $n-r$ elements that do not need to be separated, then place the remaining $r$ elements into the $n-r+1$ "slots" (between each neighbouring elements already placed, and the two ends). The total number of permutations is $\boxed{(n-r)!\:\:^{(n-r+1)}P_r}$.

e.g. Ways to arrange letters abcdefg with vowels ("ae") separated: $n=7,~r=2$. Place the 5 elements "bcdfg" first $\big($(n-r)!=5!$ ways\big)$, then place a and e into the 6 "slots". There are $5!\times\:^6P_2=3600$ ways.

End of Article