More Discrete Mathematicsvia Graph Theory

Subsection2.2.1Two Motivating Examples

To get started, let's consider two typical statements in combinatorics which we might wish to prove.

These are just two of the beautiful identities hidden in Pascal's triangle. But why are they true?

There are a at least four very distinct proofs we could give of each binomial identity. The next activities walk you through these.

Note: throughout this section especially, hints to problems are available. Try the problem first, and if you get stuck, peek at the hint.

First, let's try some proofs of Theorem 2.2.1

Note that this proof was not by any means difficult, but it did rely on an algebraic identity we have yet to prove. We will see in Activity 76 that algebraic proofs can be very messy. What's more, nothing about these proofs explain why the identity is true. They lack meaning.

Finally, here is a subtly different proof.

How are Activity 74 and Activity 75 different? The first consists of answering a single counting question in two different ways, and those ways are the two sides of the identity. Such proofs are sometimes called double counting proofs, or sometimes just combinatorial proofs. On the other hand, Activity 75 proceeds by showing two different sets have the same size, using a bijection, and shows that these two sets are counted by each side of the identity. These proofs are called bijective proofs (and are also sometimes grouped together with double counting proofs as combinatorial proofs).

Both styles of combinatorial proof have the advantage that they do an excellent job of illustrating what is really going on in an identity. They reinforce our understanding of how to solve counting problems and our understanding of basic combinatorial principles.

This is not to say that other proof techniques, especially mathematical induction, are not also helpful. Inductive proofs demonstrate the importance of the recursive nature of combinatorics. Even if we didn't know what Pascal's triangle told us about the real world, we would see that the identity was true entirely based on the recursive definition of its entries.

Now here are four proofs of Theorem 2.2.2.

There are lots of ways to give a combinatorial proof. Here is one.

We will not give a bijective proof, although you might include this as part of the above if you didn't see why \(2^n\) was the number of subsets of \([n]\text{.}\) Instead, you might see directly that \(2^n\) is the number of \(n\)-bit strings (by writing the numbers 0 through \(2^n - 1\) in binary) and then define a bijection from \(n\)-bit strings to subsets of \([n]\text{.}\)

Finally, here is a clever proof of the identity.

This use of the binomial theorem is an example of one of the many uses for generating functions which we will return to later. For now, you might enjoy plugging in other values to the binomial theorem to uncover new binomial identities.

Subsection2.2.2Interlude: The Sum and Product Principles

Any proof you write in mathematics must assume some foundational principles. In Euclidean geometry, you have axioms, common notions, and often other propositions, used as justification in your proof. Let's pause to consider two foundational principles in combinatorics that, while intuitively obvious, are worth pointing out as foundational.

When solving a counting question, it is often advantageous to break the problem into parts. If you think of the counting question as asking how many ways there are to complete a task, then you might break that task up in various ways, count the number of ways to complete each sub-task, and them combine those somehow to get the number of ways to complete the overall task. How do you combine them?

Note, while both the sum and product principle are true for more than two subtasks, which you could prove easily by induction from the versions given above. But how do we know these principles are true?

To make these principles more mathematically rigorous, consider operations on sets.

This suggests that the union of (disjoint) sets somehow corresponds to the disjunction (or) of completing tasks. You might guess that the set operation that corresponds to conjunction (and) of tasks is set intersection. But this cannot be correct: the intersection of two sets is no larger than the smallest of the two sets, while combining tasks with conjunction apparently corresponds to multiplication.

A better way to think of the conjunction is as concatenation. You are performing one task, followed by the other. Recall that \(A \times B = \{(a,b) \st a \in A, b \in B\}\) is the Cartesian product of \(A\) and \(B\text{;}\) the set of all ordered pairs where the first element comes from \(A\) and the second from \(B\text{.}\) This is exactly what we need.

We could prove these two propositions without too much trouble. Then we must explain what they have to do with the sum and product principle.

The previous activity might obscure an important subtlety. Perhaps you said that the set \(A\) corresponds to the face cards (or to the set of outcomes of the task of selecting a face card) and the set \(B\) corresponded to the black cards. The set of outcomes of picking a two card stack is exactly then \(A \times B\text{,}\) so there are \(4\cdot 5 = 20\) outcomes. This is completely correct. But does it generalize?

The Product Principle is not exactly analogous to finding the cardinality of a Cartesian product after all, since tasks \(A\) and \(B\) do not need to be disjoint. How do we make sense of the Product Principle then?

To illustrate just how fundamental these two principles are, here are a few counting problems that can be solved with them. For each of these, say exactly where and how the sum and product principles are used.

The last part of the previous activity illustrates what can go wrong if the sets \(A\) and \(B\) are not disjoint. In general, we have,

This is an example of the Principle of Inclusion/Exclusion, which we will investigate further later.

This next set of questions you can answer entirely using the product principle. While all the activities ask questions with a general \(n\) and \(k\text{,}\) it would be a good idea to first try to answer the corresponding question with specific numbers and then generalize.

The last activity is an example of a permutation. We are asking how to arrange \(k\) of the \(n\) kids (arranged by which fruit they get). There are \(n!\) ways to arrange \(n\) elements, so there are \(n!\) permutations of \(n\) elements. Often we only want to arrange some of these, so we would consider a \(k\)-permutation. We will use this often enough that it deserves its own notation.

Some other examples of questions where the answer is a permutation:

• How many 5-letter “words” (i.e., strings of symbols) contain no repeated letters? There are 26 choices for the first letter, 25 for the second, 24 for the third, 23 for the fourth and 22 for the fifth, so there are \(26\cdot 25 \cdot 24 \cdot 23 \cdot 22 = P(26,5)\) such words.

• How many different shuffled decks of cards are possible? There are 52 choices for the bottom card, 51 for the next, and so on. So the answer is \(P(52,52) = 52!\)

• How many injective functions from \([k]\) to \([n]\) are there? There are \(n\) choices for where 1 is sent, \(n-1\) choices for where \(2\) is sent (since the function is injective, 2 cannot be sent to the same element as 1), and so on. So the answer is \(P(n,k)\text{.}\)

While we are looking at permutations, let's also consider their counterpart, combinations. The key distinction is that while a permutation counts different arrangements as different outcomes, a combination does not.

Hopefully you realized that the number of \(k\)-combinations of \(n\) elements is just \(\binom{n}{k}\text{.}\) This makes sense: you just need to choose which elements to take, you don't need to arrange them.

Notice though that combinations and permutations are related in some way. What is that way? Well, once you have chosen \(k\) elements from an \(n\)-element set, you could then arrange those \(k\) elements to get a permutation.

There is nothing special about 26 and 5 in the above activity.

Notice that the only thing we needed to find the algebraic formula for binomial coefficients was the product principle and a willingness to solve a counting problem in two ways. In Section 2.3 we will consider this formula again from the other direction.

Subsection2.2.3More Proofs

We will use the proof techniques of double counting and bijections throughout the rest of the book, but for now, let's practice a bit. The activities below ask you to give a combinatorial proof, and often also an alternative proof that has some nice features.

The reader should attempt an algebraic proof of the above result using the factorial formula for \(\binom{n}{k}\text{.}\)

You could also attempt an algebraic proof or perhaps a geometric proof making use of figures consisting of triangular numbers. Also, as a challenge, the reader could formulate a similar result involving \(\binom{a + b + c}{3}\) and a corresponding proof.

Becoming an expert in combinatorial proof will help you solve actual counting problems. For example, you might wonder how many positive integers have their digits in strictly increasing order.

Now back to some combinatorial proofs.

Some other ways to approach the previous activity might be one or more of the following: \(n2^{n - 1}\) looks like a derivative, so try differentiating \(\left( 1 + x \right)^{n}\text{;}\) a reverse and add approach also works; or, first prove \(k \binom{n}{k} = n \binom{n - 1}{k - 1}\) and then use it.

The above activity illustrates another important reason to use combinatorial proofs: to establish recurrence relations. The next identity is also a recurrence, this time about derangements.

Later we will use the Principle of Inclusion/Exclusion to derive a formula for \(d_{n}\) from which the new recursion \(d_{n} = nd_{n - 1} + \left( - 1 \right)^{n}\text{,}\) and the above recursion, can be derived.

Let's get back to binomial identities.

An alternate algebraic proof is less interesting: Extract the coefficient of \(x^{n}\) from both sides of \(\left\lbrack \left( x + 1 \right)^{n} \right\rbrack^{2} = \left(x + 1 \right)^{2n}\)

For a non-combinatorial proof of the above, attempting a proof by mathematical induction is an easy option. An algebraic approach is not!

If you spend enough time working on these proofs, you might find yourself discovering new identities that use the same basic setup.

The previous identity can also be established using a collapsing sum or induction proof.

To close this section, let's return to a binomial identity we considered before, and consider a few additional proofs.