¶ Summary of Counting Results

• Permutations of $nn$ objects: $n!n!$
• $kk$-permutations of $nn$ objects: ${A}_{n}^{k}=n!\mathrm{/}\left(n-k\right)!A^k_n=n!/\left(n-k\right)!$
• Combinations (binomial coefficient) of $kk$ out of $nn$ objects:

${C}_{n}^{k}=\left(\genfrac{}{}{0px}{}{n}{k}\right)=\frac{n!}{k!\left(n-k\right)!}C^k_n=\displaystyle\binom\left\{n\right\}\left\{k\right\}=\frac\left\{n!\right\}\left\{k!\left(n-k\right)!\right\}$

• Partitions (multinomial coefficient) of $nn$ objects into $rr$ groups, with the $ii$th group having ${n}_{i}n_i$ objects:

$\left(\genfrac{}{}{0px}{}{n}{{n}_{1},{n}_{2},\dots ,{n}_{r}}\right)=\frac{n!}{{n}_{1}!{n}_{2}!\dots {n}_{r}!}\displaystyle\binom\left\{n\right\}\left\{n_1,n_2,\dots,n_r\right\}=\frac\left\{n!\right\}\left\{n_1!n_2!\dots n_r!\right\}$

¶ Table 1.1. Shiryaev (2016). The results on the numbers of samples of size $nn$ from an urn with $MM$ balls.

Ordered Sample Unordered Sample
With Replacement ${M}^{n}M^n$ ${C}_{M+n-1}^{n}C_\left\{M+n-1\right\}^n$
Without Replacement ${A}_{M}^{n}A^n_M$ ${C}_{M}^{n}C^n_M$

¶ Sampling with Replacement

This is an experiment in which at each step one ball is drawn at random and returned again.

The balls are numbered $1,\dots ,M1,\dots,M$.

• Ordered Samples of $nn$ balls: $\left({a}_{1},\dots ,{a}_{n}\right)\left(a_1,\dots,a_n\right)$
• Unordered Samples of $nn$ balls: $\left[{a}_{1},\dots ,{a}_{n}\right]\left[a_1,\dots,a_n\right]$

¶ Ordered Samples

Sample space:

Number of (different) outcomes: arrangements/permutation of $nn$ out of $MM$ elements with repetitions:

$N\left(\mathrm{\Omega }\right)={M}^{n}N\left(\Omega\right)=M^n$

¶ Unordered Samples

Sample space:

Number of (different) outcomes: combinations of $nn$ out of $MM$ elements with repetitions:

$N\left(\mathrm{\Omega }\right)=N\left(M,n\right)={C}_{M+n-1}^{n}=\left(\genfrac{}{}{0px}{}{M+n-1}{n}\right)=\frac{\left(M+n-1\right)!}{n!\left(M-1\right)!}N\left(\Omega\right)=N\left(M,n\right)=C^\left\{n\right\}_\left\{M+n-1\right\}=\binom\left\{M+n-1\right\}\left\{n\right\}=\frac\left\{\left(M+n-1\right)!\right\}\left\{n!\left(M-1\right)!\right\}$

Binomial coefficient notation:

${C}_{n}^{k}=\left(\genfrac{}{}{0px}{}{n}{k}\right)=\frac{n!}{k!\left(n-k\right)!}C^k_n=\binom\left\{n\right\}\left\{k\right\}=\frac\left\{n!\right\}\left\{k!\left(n-k\right)!\right\}$

¶ Sampling without Replacement

This is an experiment in which the selected balls $\left(n\le M\right)\left(n\leq M\right)$ are not returned.

¶ Ordered Samples

Sample space:

Number of (different) outcomes: arrangements/permutation of $nn$ out of $MM$ elements without repetitions:

$N\left(\mathrm{\Omega }\right)=\left(M{\right)}_{n}={A}_{M}^{n}=M\left(M-1\right)\dots \left(M-n+1\right)=\frac{M!}{\left(M-n\right)!}N\left(\Omega\right)=\left(M\right)_n=A^n_M=M\left(M-1\right)\dots \left(M-n+1\right)=\frac\left\{M!\right\}\left\{\left(M-n\right)!\right\}$

¶ Unordered Samples

Sample space:

Number of (different) outcomes: combinations of $nn$ out of $MM$ elements without repetitions:

$N\left(\mathrm{\Omega }\right)={C}_{M}^{n}=\left(\genfrac{}{}{0px}{}{M}{n}\right)=\frac{M!}{n!\left(M-n\right)!}N\left(\Omega\right)=C^\left\{n\right\}_\left\{M\right\}=\binom\left\{M\right\}\left\{n\right\}=\frac\left\{M!\right\}\left\{n!\left(M-n\right)!\right\}$

The following relationship holds:

${C}_{M}^{n}\cdot n!={A}_{M}^{n}C^n_M\cdot n!=A^n_M$