Permutations and Combinations Definition: We define P(n,r), where n and r are natural numbers, as the cardinality of the set of injections from r into n. This can be understood naively as the number of different ways to arrange r distinct elements of an n-element set in order, but it should be easy enough to see that this amounts to the same thing. Theorem: P(n,r) = n!/(n-r)! Proof: Use the counting principle for uniformly branching trees on the tree of injections with natural number domain and codomain n ordered by inclusion. At each level r<=n, one has the injections with domain r; one has n-r choices for the value at r of each ``child'' at level r+1. So this is a uniformly branching tree with branching function b(r) = n-r. P(n,r) will be the cardinality of level r of the tree, which is Pi{i<r}(n-r) = n*(n-1)*...*(n-(r-1)) = n!/(n-r)!. Definition: We define C(n,r), where n and r are natural numbers, as the cardinality of the set of subsets of n of size r. Informally, C(n,r) is the number of ways to choose r elements from a set of size n, without reference to order. Theorem: C(n,r) = P(n,r)/r! = n!/(r!*(n-r)!) Proof: We show that C(n,r)*r! = P(n,r), by showing that the set of all injections from r to n is the union of a family of C(n,r) disjoint sets each of which has r! elements, and appealing to the basic counting principle for multiplication (and implicitly to a definition of division!) C(n,r) is well-defined because we know that there are 2^n subsets of n (by an earlier example) so any set of subsets of n is finite (because any subset of a finite set is finite). There are C(n,r) subsets of n of size r. For each subset A of n with |A| = r, consider the set of injections from r into n with range A. We claim that there are r! such injections. This is the trickiest part of this proof (at least as I see it now). I exhibit the bijection I use, and indicate a proof of the details. The idea is that we know already that r! is the size of the set of all bijections between r and r. Choose a particular injection f from r to n with range A (say the unique increasing one). We associate each bijection (r,g,r) with an injection (r,f o g,n); it turns out that this is a bijection! It is a basic property of injections that for any functions g and h, and injection f, f o g = f o h -> g = h. This is part of what is needed to show that the map introduced in the previous paragraph is an injection. And this follows immediately from the definition of an injection: f(g(x)) = f(h(x)) -> g(x) = h(x) for any x, so g = h. This shows that our map (g |-> fog) is an injection. We also need to argue that it is an injection. Let f' be any injection from r to n with range A; we want to show that it is of the form f o g for some bijection g from r to r. For any k < r, we define g(k) as f{-1}(f'(r)), so that f(g(r)) = f'(r), which is what is wanted. So we have shown how to partition the injections from r into n into C(n,r) pairwise disjoint families of sets of size r!, from which the theorem follows. Definition of Division: We define m/n as the unique r such that r*n = m, in case there is such an r. We leave open how m/n is to be defined in other cases. The uniqueness of m/n (when it is defined) follows from the cancellation property of multiplication in our formal arithmetic, which you have been asked to verify. Pascal's Triangle We verify the well-known relationships which allow us to draw Pascal's Triangle: Theorem: C(n,0) = C(n,n) = 1; C(n+1,r+1) = C(n,r) + C(n,r+1) C(n,0) = 1 because there is only one empty subset {} of n. C(n,n) = 1 because there is only one n-element subset (n itself) of n. C(n+1,r+1) is defined as the cardinality of the set of subsets of n+1 with cardinality r+1. We divide these sets into two obviously disjoint subsets: the ones which contain n (the largest element of n+1) and the ones which do not. Each subset A of n+1 which contains n and is of size r+1 corresponds to the subset A-{n} of n, which we know is of size r. We claim that this defines a bijection between the set of subsets of n of size r and the set of subsets of n+1 of size r+1 which contain n; we don't prove this, but we claim that it is obvious; it follows that the set of subsets of n+1 of size r+1 which contain n is of size C(n,r). Each subset of n+1 of size r+1 which does not contain n is a subset of n of size r+1 and vice versa; we know that there are C(n,r+1) of these. We have divided the set of subsets of n=1 of size r+1 into two sets (those which contain n and those which do not) which are clearly disjoint and cover the whole set. One is of cardinality C(n,r) and the other of size C(n,r+1); we can apply the basic counting principle of addition to conclude that the whole set is of cardinality C(n,r) + C(n,r+1) as desired. Notice that this theorem does not depend on the preceding theorem evaluating C(n,r), and also that it looks like a kind of recursive definition of C(n,r). It is possible to prove the preceding theorem by induction using this theorem. Theorem: C(n,r) = n!/(r!*(n-r)!) (it is important to note that n>=r is required). Proof (by induction on n): Basis step: Clearly C(0,0) = 1 = 0!/(0!*(0-0)!) = 1 (0! is defined as 1). So for all r <= 0, C(0,r) = 0!/(r!*(0-r)!) (since r<=0 iff r = 0). Induction step: Suppose that for all r <= n, C(n,r) = n!/(r!*(n-r)!). We show that for all r <= n+1, C(n+1,r) = (n+1)!/(r!*((n+1)-r)!). Case 1: r = n+1 By the preceding theorem, C(n+1,n+1) = 1 = (n+1!)/((n+1)!*((n+1)-(n+1)!)) = (n+1)!/((n+1)!*0!) = (n+1)!/(n+1)! Case 2: r = 0 By the preceding theorem, C(n+1,0) = 1 = (n+1!)/(0!*((n+1)-0)!) = (n+1)!/(n+1)! Case 3: 1 <= r <= n In all these cases, C(n+1,r) = C(n,r) + C(n,r-1) (by the previous theorem) = n!/(r!*(n-r)!) + n!/((r-1)!*(n-(r-1))!) = (n!*(n-(r-1)))/(r!*(n-(r-1))!) + (n!*r)/(r!*(n-(r-1))!) (on each side, we promote a factorial in the denominator and multiply by the appropriate amount in the numerator to preserve the value of the ratio) = (n!*(((n+1)-r)+r))/(r!*((n+1)-r)!) (here we add the numerators and convert n-(r-1) to the equivalent form (n+1)-r) = (n!*(n+1))/(r!*((n+1)-r)!) (trivial) = (n+1)!/(r!*((n+1)-r)!) which is what was to be proved. So we have a second proof of the same theorem on evaluation of C(n,r). Another useful relationship which follows easily from the formula using factorials is C(n,r+1) = C(n,r)*((n-r)/(r+1))