12. Combinatorial Proofs

Now let us go to the last topic for today's lecture, namely combinatorial proofs, and again I am sure that you have studied it during your high school. So what exactly are combinatorial proofs? These are some common proof strategies which we often use in combinatorics. Namely, it's a counting argument to prove identities where you have something on the left-hand side and something on your right-hand side, and you want to prove mathematically that your expression on the left-hand side and the right-hand side are the same.

In this chunk, we are introduced to combinatorial proofs, a key concept in combinatorics. Combinatorial proofs utilize counting arguments to show that two different expressions (one on the left and one on the right) represent the same quantity, without performing any algebraic expansion or simplification. This method emphasizes the idea of counting the same objects in different ways rather than confirming their equality through simplification.

Think of combinatorial proofs like counting the number of ways to choose a team of players from a larger group. Instead of calculating the total directly, you could count one way (how many players you can choose) and show that it corresponds perfectly with counting the players that are not in the team. Both methods arrive at the same answer without needing to break the counting down into smaller pieces.

But to do that, we use a counting argument and we prove that the expression on the left-hand side and the expression on the right-hand side count the same number of objects but in different ways. But nowhere in the proof do we actually expand our expressions on the left-hand side or right-hand side and show by simplification that left-hand side is the same as right-hand side. We do not do that. That is not the goal of a combinatorial proof.

This chunk emphasizes the method used in combinatorial proofs where we focus on how two expressions can be interpreted to count the same quantity in different ways. The key point here is that in combinatorial proofs, we avoid simplifying expressions; instead, we concentrate on the different interpretations of counting the same sets of objects. This is the essence of a combinatorial proof: showing equivalence through combinatorial arguments rather than algebraic manipulation.

Imagine you are organizing a party and need to count how many ways you can invite guests. One method is to count how many guests will be invited directly. Another method is to count how many guests will not be invited and subtract that from the total. Both methods tell you how many invitations you’ll send out, but they approach the problem from different angles without reducing the expressions to numbers.

Let us see a very simple combinatorial proof which you must have definitely studied. We will want to prove that the value of C(n, k) is the same as the value of C(n, n-k). Of course, one way of doing that is to expand C(n, k) and rewrite it as n!. And I expand my right-hand side. And in this case actually both the expressions are the same.

The next step is demonstrating a simple application of combinatorial proof: proving the identity C(n, k) = C(n, n-k), which expresses the concept that choosing k items from n is equivalent to leaving out n-k items. Here we can visualize that choosing k items means we are simply avoiding n-k items, and vice versa. This relationship is crucial in combinatorial proof as it shows how two counts can map to one another without the need for expansion.

Consider a box of 10 different colored balls. If you need to choose 3 balls to take home, you could think about that as selecting 3 colors. Alternatively, you could think about the 7 colors you are leaving behind. Whether you count how many ways you can select 3 balls or how many ways you can exclude 7, both perspectives count the same number of combinations.

Now let's prove an interesting combinatorial identity using combinatorial proof. This is often called Pascal's identity. So to prove this, we consider a collection of n+1 objects. The left-hand side expression C(n, k) denotes the total number of k-combinations I can have out of those n+1 objects. I have to pick k objects. I can do that in C(n+1, k) ways.

In this chunk, we begin applying combinatorial proof to a more complex identity known as Pascal's identity. We consider a set of n+1 objects and establish that the left-hand side of our identity corresponds to the total number of ways to choose k objects from these n+1 items. This serves as a foundation for breaking down the problem and showing that counting can be effectively divided into two groups, both leading to the same count.

Imagine you have 5 different fruits and you want to select 2 for a smoothie. Using Pascal’s identity, you can think of it as either picking 2 fruits including a specific one (like a banana), or picking 2 fruits excluding that banana. Each grouping represents a different way of looking at the selection, but ultimately leads to the same number of possible smoothies.

The claim is that different k-combinations that I can have out of n+1 objects can be divided into 2 groups. You consider all k-combinations that you can form out of those n+1 objects where a specific object is always present. This number is C(n, k-1).

This chunk elaborates on the counting of k-combinations concerning Pascal's identity. We categorize the selections into two distinct groups: one that includes a specific object and another that excludes it. If you include a specific object, say object X, you only need to choose (k-1) more from the remaining objects. This logical structuring allows us to break down the combinations being counted into manageable, relatable pieces, reinforcing the foundation required for combinatorial proofs.

If we stick with the fruit smoothie example, let's say the specific fruit we need to use is a banana. If we’re making a smoothie using 2 fruits, we could either select the banana plus one other fruit (which is C(4, 1) if we consider the other 4 fruits) or make a selection of 2 fruits without the banana (which is C(4, 2)). This illustrates how we can dissect a problem into simpler components and apply combinatorial reasoning.

So if I sum the total number of k-combinations that I have in category 1 and the number of k-combinations that I have in category 2, that will give me the total number of k-combinations that I can have for a set consisting of n+1 objects. And that's precisely your right-hand side. And this is a combinatorial proof because I have not expanded my left-hand side expression, I have not expanded my right-hand side expression and simplified them.

Finally, this chunk wraps up the combinatorial proof established for Pascal's identity. By summing the counts from both categories, we find that the total configurations of selecting k items from n+1 can either include or exclude the specific object. This final summation logically leads us back to the right-hand side of the identity, demonstrating the closed-loop nature of combinatorial proofs without simplifying algebraically.

Returning to our fruit selection analogy, we find that when summing the combinations using banana and without banana, we arrive at the total ways to select any two fruits from a set of five. Instead of focusing purely on the numbers, recognizing the categories and counting lends itself to understanding without losing the essence of why combinations are equal in different contexts.

--