12.3.1. Category 1 of Combinations

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 in the left-hand side and the right-hand side are the same.

In this chunk, we introduce the concept of combinatorial proofs. A combinatorial proof is a method used in counting problems, where we want to demonstrate that two expressions count the same set of objects in different ways. Rather than simplifying expressions or expanding them mathematically, we focus on the way the objects can be counted. For instance, in a typical identity, we might have a left-hand side (LHS) and a right-hand side (RHS). The goal is to provide a reasoning or counting argument that shows both sides represent the same quantity, hence proving their equivalence.

Think of it like counting the number of guests at a party. If you count guests as they arrive (left-hand side), and your friend counts them as they leave (right-hand side), both methods should result in the same total number of guests, even though the methods of counting are different.

But to do that we use a counting argument and we prove that the expression in the left-hand side and the expression on the right-hand side count the same number of objects but in different ways.

This chunk explains the key aspect of combinatorial proofs, which involves counting arguments. A counting argument is where we describe how the same set of objects can be counted in two different ways. The essence of a combinatorial proof is that no actual algebraic manipulation or simplification of expressions is performed. Instead, we focus on the interpretations of the quantities represented by the expressions, which leads us to conclude that both sides count the same thing.

Imagine a classroom where students can sit in two different ways: some students choose seats based on their favorite spots (one counting method), while others line up by height (another counting method). As we analyze how both groups can count the same students, we see that both interpretations lead to the same total number of students in the room.

Suppose you are given C objects. Then your left-hand side is nothing but the number of ways in which you can pick k objects out of those C objects. That's the interpretation of the C(k). Now it turns out that for each of the ways in which you can select k objects, there is a way of excluding C−k objects.

In this chunk, we observe how to apply a counting argument to C objects. The LHS is interpreted as the selection of k objects from a total of C, which can be done in C(k) ways. By focusing on the number of ways to exclude (C-k) objects instead, we can derive a matching method that provides the same total count through a different perspective. This insight reinforces the idea that looking at what we don't choose can be just as informative as looking at what we do choose.

Imagine having a basket of 10 fruits and deciding to pick 3. Instead of thinking about which 3 fruits to take, consider which 7 fruits you will leave behind. Both methods ultimately lead to the same conclusion about the combinations available.

Now let's prove an interesting combinatorial identity using combinatorial proof. This is often called Pascal's identity. So to prove this, consider a collection of C+1 objects.

Pascal's identity is a specific example where we can apply combinatorial proofs to establish an identity involving combinations. The identity states that the number of ways to choose k objects from C+1 objects can be expressed as the sum of the number of ways to choose k-1 objects from C objects and the number of ways to choose k objects from C objects. Here, the LHS represents a scenario with one additional object included, leading us to analyze how two groups of selections can be formed based on whether or not that additional object is chosen.

Imagine a bag containing 11 different candies. If you want to choose 3 candies, you could either choose one specific candy first (e.g., a chocolate), which leaves you with 10 other candies to choose the remaining 2 from, or you could choose from the rest of the 10 candies if you decide not to take that specific candy at all. Both paths result in the same number of ways to make your selection, illustrating Pascal's identity.

--