## Chapter 4 combinatorial arguments

The four that are designated as possibly on the test start with a (T). The philosophy of a combinatorial proof is that we do not dwell on the numbers we are looking at (or the formulas representing the numbers) but rather we think about the structures (i.e. various sets) that we know have that many elements. By setting up correspondences between such structures we establish relationships between the corresponding formulas.

• 4-3 Number 48. C(n,r)C(r,k) = C(n,k) C(n-k,r-k)

I don't feel like writing this one out in long detail. If you have trouble with what I now say, just read some of the others first and then come back to it. The lesson though is that combinatorial proofs can be extemely short and efficient (often called elegant).

The LHS clearly does the following. Take a set with n elements and choose an r element subset of it. Then choose a k element subset of the r element set. We have just counted the set of pairs of set (A,B) where A is an r element set and B is a k element subset of it.

The RHS (with this in mind) can be viewed as first pick B and then think about all the A that can be associated with B. Well not exactly, instead think about all the A-B. So, (A,B) can be uniquely associated with (B, A-B) (1-1 correspondence). What is (B, A-B)? Well pick a k element set B, and then pick a subset of the complement of B which has r-k elements. That is exactly what the RHS is counting.

• 4-3 Number 50. C(2n,2)=2C(n,2)+n^2

LHS: you have 2n elements, pick two of them. Period.

RHS: take 2n elements and split it into two sets of size n. Either pick two elements from the first set, or pick 2 elements from the second set, or pick one from the first and one from the second.

We counted the same set (that is the set of 2 element subsets of {1,..., 2n}) in two different ways. So the resulting quantities are equal.

• (T) 4-3 Number 59. Use paths to prove that C(n+r+1,r)=SUM{C(n+k,k): k=0,r}

We are going to think about paths from the integer pair (0,0) to the integer pair (n,r) on the plane in which a path means move 1 unit to the right or 1 unit up the page. Just draw yourself a picture to visualize this. We can describe a path by a sequence of commands
RURRRUURR etc. which means move Right, then Up then Right 3 times then Up twice and finally Right twice. This corresponds to the chain of positions:
(0,0) - (1,0) - (1,1) - (2,1) - (3,1) - (4,1) - (4,2) - (4,3) - (5,3) - (6,3).
Any rearrangement of 6 R's and 3 U's will get you to (6,3). So the set of paths from (0,0) to (n,m) is in 1-1 correspondence with the set of words that can be made from n R's and m U's. This latter set has size C(n+m,m) (which also equals C(n+m,n) of course).

So the number on the LHS in the question can be regarded as the number of elements in the set of paths from (0,0) to (n+1,r). Let us see if we can show that this set can also be counted with the formula on the RHS of the equation. We have a sum with r+1 terms so we can expect that we should break the set of paths into r+1 disjoint sets.

For each k from 0 to r, suppose first move UUU until we get to within k steps of the top. E.g. k=0 move straight up to (0,r), for k=1 move straight up to (0,r-1), etc. We set Lk to be the set of paths that first move to (0,r-k) and then immediately move R and then continue in any fashion after that. This means that Lk is disjoint from Lj for distinct j,k and every path is in exactly one of the Lk's. So the total number of paths is just the sum of the number of paths in each Lk. Well Lk is the set of paths from (1,r-k) to (n+1,r). Clearly this is the same number as the set of paths from (0,0) to (n,k) (i.e. we must n to the right and k up). The rest is easy.

• (T) 4-6 Number 45. Using sequences of numbers: show that Number of r element subsets of {1,...,n} with repetitions is the same as the number of r elements subsets of {1,..., n+r-1} without repetitions.

Set up a 1-1 correspondence between the two sets. In this way we have a new proof that the set of r element subset of {1,..., n} with repetitions allowed is equal to C(n+r-1,r).

We will represent an r element subset of {1,... , n} with repetitions as a non-decreasing sequence of integers from 1 to n. I.e. {1,2,1} is the same as {1,1,2}. So the easiest way to view a faithful listing is as [1,1,2], etc. So our map should set up a 1-1 correspondence between such non-decreasing sequences [k1,k2, ... ,kr] of elements between 1 to n and r element subsets of {1, ... , n+r-1} with no repetitions. The trick is easy:
[k1, k2, ..., kr] ----> {k1, k2+1, k3+2, ..., kj+(j-1), ..., kr +(r-1)}
It is routine (BUT NECESSARY!) to check that this is indeed a 1-1 correspondence between the two sets. That is each r element subset of {1,2, ... , n+r-1} is the image of some sequence [k1,..., kr] (ONTO), and if we start with two distinct sequences of k's we end up with two distinct r element sets (ONE TO ONE).

• (T) Pascal's Identity.
This is the pardigm. We are to prove using sets and functions that C(n+1,r) = C(n,r-1) + C(n,r).

We fix any set of size n+1, e.g. A={1,2,..., n+1}. Let L denote the collection of all possible r element subsets of A. Split L into two disjoint pieces: L0 and L1. A set b from L goes into L0 if n+1 is a member of b, otherwise b goes into L1.

Since L0 and L1 are disjoint, the cardinality of their union is just the sum of their cardinalities.

What is the cardinality of L0? We will find a 1-1 correspondence between the set L0 and the set K consisting of all the r-1 sized subsets of the set B={1,..., n}. If we do so then we know that L0 has the same number of elements as the set of all r-1 sized subsets of B. Of course this common size is, by definition, equal to C(n,r-1).

The bijection from L0 to K0 is defined as follows: given a set S in L0, define f(S) to be simply S - {n+1}. We must check that f is 1-1 and onto. f is onto, for if T is an r-1 sized subset of B, then S = (T union {n+1}) is an r-sized subset of A and clearly f(S) = T. Now, why is f 1-1? Well suppose that S and S' are two distinct members of L0. They both contain n+1 but are distinct, hence if we remove n+1 from each of them the resulting sets are still distinct. Since this is the definition of the function f, it follows that f(S) is distinct from f(S'). This is the definition of a 1-1 function, hence f is 1-1.

Now we prove that L1 has size C(n,r). This is actually much easier. Clearly every member of L1 is a subset of {1,..., n} and every r element subset of {1,..., n} is a member of L1.

Summary: we have proved this identity combinatorially in the following sense. We found a set whose size is canonically represented by the expression on the LHS of the equation (namely the r-element subsets of A). Next we found a set whose size is canonically expressed by the expression on the RHS of the equation: namely the r-1 sized subsets of {1,..., n} unioned with the r sized subset of {1,..., n}. Finally we established a bijection between the set for the LHS and the set for the RHS.

• (T) Van der Monde's for m=8, n=5, r=4 (Theorem 5 4-3).

We are to prove C(13,4) = SUM{ C(8,4-k)C(5,k) : k=0,4 }.

A set which canonically (or clearly) has sized C(13,4) is the set of 4 element subsets of A = {a1, a2, ..., a13}.

Here is our choice for a set which clearly has the size on the RHS. Let B = {b1,..., b8} and C={c1,..., c5}. For each k from 0 to 4, we can interpret C(8,4-k) as the set of 4-k sized subsets of B and C(5,k) as the set of k sized subsets of C.

Also, then, C(8,4-k)*C(5,k) can be thought of as the collection, call it Lk, of all pairs of sets, the first member of which is a 4-k sized subset of B and the second member of which is a k sized subset of C.

So the set for the whole RHS is the following union:

L0 union L1 union L2 union L3 union L4

Therefore to do this question we want to establish a correspondence between the set representing the LHS and the set representing the RHS.

It is simple: Given a set S of size 4 contained in A we define f(S) to be the ordered pair (S1,S2) as follows. We look at S intersection {a1, ..., a8} and we make S1 into exactly those bi's such that the corresponding ai's (i from 1 to 8) as are in S. Similarly we set S2 to be the rather obvious subset of {c1,... , c5} corresponding to S intersection {a9,a10, a11, a12, 13}. That is, ci is in S2 iff a(8+i) is in S. We set k to be the size of S2 and check that S1 is obviously of size (4-k). It should be clear that this is the desired correspondence.

• 4-3 Number 33. C(n+1,k) = (n+1) C(n,k-1) /k

This is a little harder. On the LHS we will have the family of k sized subsets of {1,..., n+1}.

Our view of the RHS is a little more complicated. Ignore the divide by k for a second. That is, just think about the quantity (n+1) C(n,k-1) (try to think about quantities as representing sets of that size and be prepared to flip back and forth between the views). If we take n+1 different sets of size n, and for each of those sets we take all the k-1 sized subsets, we will have a total of (n+1) C(n,k-1) sets. For each i, think of Ai as the set from 1 up to n+1 with i removed. Then let Li denote the set of all k-1 sized subsets of Ai. If we treat the Li as pairwise disjoint (this can be made formal by using different symbols to denote the members of Ai for each i but maybe it's not necessary, just agree to treat the members of Li as distinct from the members of Lj). Actually the best way is to identify a set S from Li with the ordered pair (S,i). In this way we can remember which family S came from. So if k=2, then {1,2} comes from L3, L4, L5, ... but we instead use ({1,2},3), ({1,2},4), ... as the objects that we are counting. So let L denote the union of all the Li.

Finally we establish a function from L onto the set of k sized subsets of {1,..., n+1} (i.e. the LHS set). For each member of L, say (S,i), we define f(S,i) to be simply S union {i}. The result is a set of size k, since S had size k-1 and i was not in S since S came from Li which makes it a subset of {1, ..., n+1 - {i}.

We examine this function f for a minute. This function is ONTO the set of k sized subsets of {1, ..., n+1}. This is pretty obvious. Think about it for a minute and realize that for each k sized set T contained in {1, ... , n+1}, there are exactly k many (Si,i) which are sent to T by f. Indeed, for each i in T, let Si = T - {i} and observe that f( Si, i ) = T. And these are the only ones that are sent to T. This means the size of the set on the RHS is exactly k times the size of the set on the LHS. This completes the proof. This was just a generalization of the idea that 1-1 functions give you that the sets are exactly the same size. A function which is everywhere 2-1 obviously divides the size by 2, and so on.