2 years ago

# Probability and Statistics

#### Combinations:

Let $r,n$ are non-negative integers, a $r$-combination of n objects is an unordered selection of $r$ of $n$ objects. It can also be called combination of $n$ objects taken $r$ at a time.A $r$-combination of $n$ object simply means a subset of size $r$ from set of $n$ objects.

If $S=\{a,b,c\}$, then
$1$-combinations of $S$ are $\{a\},\{b\},\{c\}$
$2$-combinations of $S$ are $\{a,b\},\{a,c\},\{b,c\}$
$3$-combinations of $S$ are $\{a,b,c\}$ and there are no 4-combinations as not possible, and.
there is a $0$-combination of S (empty one).
Notation:- $\binom{n}{r} :=$number of $r$-combinations of $n$ objects. These are called binomial coefficient because of the role it played in binomial theorem(we will see later)

From above example we can see that $\binom{3}{0}=1$,$\binom{3}{1}=3$, $\binom{3}{2}=3$,$\binom{3}{3}=1$ and $\binom{3}{4}=0$

Theorem: For $0\le r\le n$, $^nP_r=r!\binom{n}{r}$, Hence $\binom{n}{r}=\frac{n!}{r!(n-r)!}$
proof:
Let $S$ be set of an $n$ objects. Each $r-$ permutation of $S$ can be made by performing following procedure that is broken down into sequence of two tasks,
task-1: choose r objects from S,
task-2: arrange the chosen r objects in some order.
and here task-1 can be done in $\binom{n}{r}$ ways, and task-2 can be done in $r!$ ways, so this procedure can be done in $\binom{n}{r}r!$ ways.
$\therefore~ ^nP_r=\binom{n}{r}r! \Rightarrow \binom{n}{r}=\frac{n!}{r!(n-r)!}$
Note: $\binom{n}{r}=\binom{n}{n-r}$

Example: Twenty five points are chosen in the plane out of which 8 points are collinear and no three points come from outside these 8 points are collinear.How many lines do they determine? How many triangle do they determine?
solution: we know that any two points decides unique line, so we are interested in counting $2$ point subsets of given twenty five points, there are $\binom{25}{2}$ $2$ point subsets ,but $\binom{8}{2}$ $2$ point subsets give same line (as 8 of 25 points are collinear ) so the answer is $\binom{25}{2}-\binom{8}{2} +1$
when it comes to forming a triangle we need $3$ point subsets of given twenty give points that do not form a triangle and $3$ point subsets of points from triangle only when all come from $8$ particular set of points, so $\binom{25}{3}$ will not be correct, but can be fixed as we know exactly $\binom{25}{3}$ of these won't make triangle, hence these $25$ points determine $\binom{25}{3}-\binom{8}{3}$