Counting
Counting assumes discrete uniform law, where \(\Omega\) consists of \(n\) equally likely elements. If \(A\) is a subset of \(k\) elements, then \(\mathbb P(A)=\frac{k}{n}\).
Basic counting principle
An \(k\)-long sequence of \(a_i\) variables, each being able to take \(n_i\) values (\(i=1,\dots,k\)), can generate a total of \(N=n_1n_2\dots n_k\) outcomes.
| Values | Number of outcomes |
|---|---|
| \(a_i\in\{0,1\}\), with \(\lvert A\rvert=n=k\) | \(2^n\) (number of all possible subsets in \(A\)) |
| \(a_i\in A\), with \(\lvert A\rvert=n\) | \(n^k\) |
| \(a_i\in\{1,\dots n\}\), \(k\le n\) without repetitions |
\(\displaystyle n\cdot(n-1)\dots (n-k+1)=\frac{n!}{(n-k)!}\) |
Combinations
There are \(\frac{n!}{(n-k)!}\) ways to create a subset of \(k\) elements out of a group of \(n\) elements, which in turn can be reordered in \(k!\) ways. Therefore, there are \(\frac{n!}{(n-k)!k!}\) of possible \(k\)-element subsets of a given \(n\)-element set. Few remarks.
| Formula | Equivalent form |
|---|---|
| \(0!\) | 1 |
| \(\displaystyle{n\choose k}\) or \(\displaystyle{n\choose n-k}\) | \(\displaystyle\frac{n!}{k!(n-k)!}\) |
| \(\displaystyle{n\choose n}\) or \(\displaystyle{n\choose 0}\) | \(1\) |
| \(\displaystyle k{n\choose k}\) | \(\displaystyle n{n-1\choose k-1}\) |
| \(\displaystyle{n\choose k}\) | \(\displaystyle\sum_{i=0}^k{m\choose i}{n-m\choose k-i}, n\ge m\) |
| \(\displaystyle\sum_{k=0}^n{n\choose k}\) | \(2^n\) |
| \(\displaystyle\sum_{k=0}^nk{n\choose k}\) | \(n2^{n-1}\) |
Binomial probability
Binomial coefficient \({k\choose x}\) is the basis of the binomial probability. Assumimg a coin with \(\mathbb P(\text{heads})=p\), the probability of \(x\) heads in \(k\) tosses is \(\mathbb P(x\text{ heads})={k\choose x}p^x(1-p)^{k-x}\).
- \(p^x\) is the probability of tossing \(x\) heads;
- \((1-p)^{k-x}\) is the probability of tossing \(k-x\) tails;
- \(p^x(1-p)^{k-x}\) is the joint probability of the above two independent events; and
- \({k\choose x}p^x(1-p)^{k-x}\) is the additive probability of the mutually exclusive events.
Many problems can be reduced to binomial probability. Start from counting how may event(s) are associated with probability \(p\), as well the event(s) associated with its complement \(1-p\).
If all sequences share the same probability (recall discrete uniform law), the problem reduces to counting and you can get rid of all \(p^k(1-p)^{n-k}\) occurrences. Just bear in mind that you can further breakdown the counting into products, if combinations of joint events are present, and that if conditions are in order, you need to divide by the number of occurrences that satisfy that condition.
Partitioning
More generally, a set can be partitioned in \(r\) subsets, each of cardinality \(n_i\), \(i=1,\dots,r\). In such case, the number of subsets in which partitioning could occur is \(\frac{n!}{n_1!\dots n_r!}\), which is also defined as multinomial coefficient \({n\choose n_1,\dots,n_r}\).
Go back to the syllabi breakdown.