Combinatorics/Subsets of a setThe 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 . To see this first take a set X of n elements and a subset Y of it. Now consider the following function:
Such a function is called an indicator function. If then we can represent the above function by the ntuple . This ntuple is a sufficient description of Y. By looking at the ntuple one can easily deduce Y, the positions corresponding to 1 are its members. Conversely given Y one can always construct this ntuple. So each subset corresponds with exactly one ntuple.
Now regard this ntuple as a base 2 integer
 .
Each ntuple corresponds to a unique integer (since the coefficients of each ntuple are unique) and so to a unique subset of X. The smallest i.e. 0, corresponds to the ntuple of zeros which in turn corresponds with the empty set, the largest i.e. corresponds to the ntuple of ones which in turn corresponds to X. There are such integers between 0 and (including 0 and ) and so there are subsets possible for X.
Let us now turn our attention to binomial coefficents. Given a nonnegative integer n and an integer k, the binomial coefficient is defined to be the natural number
and
where n! denotes the factorial of n.
is read as n choose k.
The most important result concerning binomial coefficients is as follows:
 Theorem:Let X be an norder set. Then the number of its korder subsets is
Proof: Let . 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 n1 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 (nk)! permutations of the elements not in Y. If we attach any one of these (nk)! 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 korder subsets. Thus the total possible permutations would be T.k!(nk)! where T is the number of korder subsets. That is because total permutations = adding k!(nk)! the number of times equal to the number of korder subsets = T.k!(nk)!. Now this number must be equal to n! and so we have T = The number of korder subsets of X = . Q.E.D.
The above proof guarantees that is an natural number, for the simple reason that it represents the number of ways of selecting a korder subset out of an norder subset. Usually whenever we have n choices and k have to be chosen we declare that the number of ways of doing this are . At that instance we are actually drawing a parallel between the choices and the elements of the norder 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
which follows directly from the definition:
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 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.