Combinatorics proof is an elegant technique in mathematics via counting the same elements in two different ways in order to prove identity. I will try to explain the basic Intuitions of this technique, including how to use it to prove simple identities. Whether you are a math student or a puzzle enthusiast, this method will give you a foundation to understand and apply this simple and elegant method.

• For those who are not familiar with “n choose k”, a good introduction can be found here.

1) Counting Students

Consider that there are$2n$ students who want to attend the “Introduction to Combinatorics” course, unfortunately, the university decides to schedule the class in a room with only $n$ seats. We need to choose a group of $n$ students that can have a seat in the class, while the others will have to watch the lectures online.

⇒* *How many possible groups of $n $students can we form? This is simply the binomial coefficient :

formula [1]

⇐ On the other hand, let’s divide the $2n$ students into two equal groups of size $n $. For a fix k, we can then choose $k** students from the first group and *n-k students from the second group,

formula [2]

Note that we don’t care about the order in which we choose the students, and we want to cover all the possible sub-group sizes i.e. any value of $k $. Therefore, we need to sum up all the values for any $k = 0,1,…,n.$

formula [3]

*⇔ ***Thus we get the same result as before:

formula [4]

2) Schrödinger Counting Cats

Suppose there’s a guy, let’s call him Schrödinger, who wants to diverge identical r+1 cats onto different **n+1 **boxes, one cat in each box. The total amount of different ways to put the cats in the boxes are simply given:

formula [5]

However, for some reason, Schrödinger doesn’t like to do things in the normal way, he wants to “ put the boxes inside the cats“ instead. Schrödinger claims that he can look at the first box and decide whether or not to put a cat inside it. Thus, we need a different approach to count the number of possible different unique diverges. (1) If he decides to place a cat inside, he will have $r$ cats left to arrange in the remaining $n$ boxes.(2) If he decides not to put a cat inside, he will have $r+1$ cats left to put in the remaining $n$ boxes.

formula [6]

Now, let’s consider the case where Schrödinger leaves the first two boxes empty. He will have r+ cats left to put in the remaining n-1 boxes. Using the same reasoning as before, we get:

formula [7]. note that (2) and (3) equal

We can continue this process until we have only one box left to put a cat in. At this point, we have r+1 cats left to put in the r+1 boxes, which can be done in only one way. Therefore, we get:

formula [8]

This **identity is remarkable because it connects two apparently unrelated concepts: the number of ways to choose **n objects out of 2n and the number of ways to choose i objects out of n and n-i objects out of the remaining n. It also shows how combinatorial arguments can be used to prove algebraic identities, and how different ways of counting the same objects can lead to elegant and surprising results.

For those interested in further reading about math and computer science, check out my** site.**