next up previous
Next: Unofficial notes on counting Up: Lecture Notes Previous: Tuesday, May 2, 2000

Wednesday, May 3, 2000

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))



Randall Holmes
2000-05-05