Combinatorics/Subsets of a set-The Binomial Coefficient

Let us now try to count subsets of a given set. We will call a set of order n if it contains n elements.

The first result that we will establish concerns the total number of subsets that a given set of order n can have. We claim that it is $2^{n}$. To see this first take a set X of n elements and a subset Y of it. Now consider the following function:

$f_{Y}(n)={\begin{cases}1,\ n\in Y\\0,\ n\notin Y\end{cases}}$

Such a function is called an indicator function. If $X=\{0,1\cdots n-1\}$ then we can represent the above function by the n-tuple $(f(0),f(1)\cdots f(n-1))$. This n-tuple is a sufficient description of Y. By looking at the n-tuple one can easily deduce Y, the positions corresponding to 1 are its members. Conversely given Y one can always construct this n-tuple. So each subset corresponds with exactly one n-tuple.

Now regard this n-tuple as a base 2 integer

$N=f(n-1)2^{n-1}+f(n-2)2^{n-2}\cdots f(1)2+f(0)$.

Each n-tuple corresponds to a unique integer (since the coefficients of each n-tuple are unique) and so to a unique subset of X. The smallest i.e. 0, corresponds to the n-tuple of zeros which in turn corresponds with the empty set, the largest i.e. $2^{n-1}+2^{n-2}\cdots 2+1=2^{n}-1$ corresponds to the n-tuple of ones which in turn corresponds to X. There are $2^{n}$ such integers between 0 and $2^{n-1}$ (including 0 and $2^{n-1}$) and so there are $2^{n}$ subsets possible for X.

Let us now turn our attention to binomial coefficents. Given a non-negative integer n and an integer k, the binomial coefficient is defined to be the natural number

${n \choose k}={\frac {n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1}}={\frac {n!}{k!(n-k)!}}\quad {\mbox{if}}\ 0\leq k\leq n\qquad (1)$

and

${n \choose k}=0\quad {\mbox{if }}k<0{\mbox{ or }}k>n$

where n! denotes the factorial of n.

${n \choose k}$ is read as n choose k.

The most important result concerning binomial coefficients is as follows:

Theorem:Let X be an n-order set. Then the number of its k-order subsets is ${n \choose k}$

Proof: Let $X=\{1,2\cdots n\}$. These numbers may be listed in various orders, called permutations. There are n! of these permutations because the first term may be any of the n numbers, the second any of the remaining n-1 numbers and so on.

Let us count these permutations in a different way now. Then we shall apply double counting as described in the previous chapter.

Let Y be a subset of X having k elements. Then there are k! permutations of the elements of Y. Similarly there are (n-k)! permutations of the elements not in Y. If we attach any one of these (n-k)! permutations to the right end of any one of the k! previous permutations, the ordered sequence of n elements thus obtained is one of the permutations of X. To get all the permutations of X we repeat the procedure with Y replaced by each of the k-order subsets. Thus the total possible permutations would be T.k!(n-k)! where T is the number of k-order subsets. That is because total permutations = adding k!(n-k)! the number of times equal to the number of k-order subsets = T.k!(n-k)!. Now this number must be equal to n! and so we have T = The number of k-order subsets of X = ${\frac {n!}{k!(n-k)!}}={n \choose k}$. Q.E.D.

The above proof guarantees that ${n \choose k}$ is an natural number, for the simple reason that it represents the number of ways of selecting a k-order subset out of an n-order subset. Usually whenever we have n choices and k have to be chosen we declare that the number of ways of doing this are ${n \choose k}$. At that instance we are actually drawing a parallel between the choices and the elements of the n-order set.

The discussion here would remain incomplete if we do not put a note about Pascal's triangle here.

Pascal's rule is the important relation

${n \choose k}+{n \choose k+1}={n+1 \choose k+1},\qquad (3)$

which follows directly from the definition:

${\begin{aligned}{n \choose k}+{n \choose k+1}&{}={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k+1)!(n-(k+1))!}}\\&{}=\left({\frac {n!(k+1)}{k!(n-k)!(k+1)}}+{\frac {n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}}\right)\\&{}=\left({\frac {n!(k+1+n-k)}{(k+1)!(n-k)!}}\right)\\&{}={\frac {(n+1)!}{(k+1)!((n+1)-(k+1))!}}\\&{}={n+1 \choose k+1}\end{aligned}}$

Pascal's rule gives rise to Pascal's triangle:

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

Row number n contains the numbers C(n, k) for k = 0,…,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that ${5 \choose 0}=1,\ {5 \choose 1}=5\ {5 \choose 2}=10$ etc. This is because of Pascal's relation proved above.

The differences between elements on other diagonals are the elements in the previous diagonal, as a consequence of Pascal's relation above.