The Art of Counting: Part I
This semester, I started auditing an introductory course in combinatorics and I began to see a more real-world side of number theory. I had previously studied this in high school, but then the only thing that was taught to us was proving certain identities the algebraic way. In this class, we’re taught how to think about each theorem like children do. Everyone smart has always told me, “If you want to master a concept, teach it to a 5-year old.”
So that’s what I plan to do here.
Example 1: The Committee Problem
To Prove:
Now think of what the RHS means. It’s just a way to choose n out of 2n things OR just decompose it as
So basically we’re choosing n things out of two groups of n. To make it easier think of it as choosing a committee of n members made of men and women. We have n total men and n total women.
Now we could choose 0 men and n women (Ha! In the ideal world, maybe). Which means we get,
Or we could choose 1 man and n-1 women or 2 men and n-2 women and so on..
Summing all these up, we get..
So you see how our proof was mostly words and not identities or anything like that. Identities help you, but mostly what’s important and what our professor, Alexander Yong, also stresses on, is intuition. About the way you’re formulating the problem.
Example 2: The Dean and his Daughter
To Prove:
Okay now for this problem, think of yourself as the dean of your college. You have a pool of applications you need to choose from for the next academic year.
Let’s say you have a fixed batch size of k students and you have n applications. You’re extremely lazy and so the way you do this is have your daughter come to the school and handpick any k of them. The number of ways she can do this is :
But now you have another problem, you have scholarship funds for m students and now you actually have to choose m students from those k students who will be lucky enough to get that scholarship. So you call your daughter again and she does the job. But how many possible ways are there to do this?
So the total number of ways that you choose m scholarship students from those n applications is:
Okay, so now we’ve formulated our LHS. Let’s look at another way the Dean has in mind. He calls his daughter first and asks her to pick m student applications at random for all the scholarship students. Since these students are then automatically admitted in the college, we now have n - m applications left and the vacant spots are k - m. So the total number of ways we can do THIS is :
And so we get our RHS. See this? This is called a combinatorial proof in many senses because it’s counting the same set twice using different approaches. And we can simply equate those counts. Let’s look at another example.
Example 3: The Superstitious Man
To Prove:
Consider this lattice shown below. It’s made of tiny unit squares and instead of being a square generalize it to a rectangle of length a and width b.
Let’s say this a park that a man is leisurely walking in. But as the title may have told you already, that man is very superstitious. He takes only North and East steps. So how many possible paths are there from the bottom left corner, the origin, (0, 0) to the top right corner of the park (a, b)?
(These are known as lattice paths)
Now, this is exactly the RHS of the equation above. So that means that we’re somehow trying to find show the LHS as the total number of paths from the origin to the top right corner. Here’s what we’re going to do. We’re going to decompose all the paths by the height at which they last cross a “fence”. And we’re going to place a fence over our lattice like this here at a -1:
So now as can be seen, the green path crosses the fence at y = 1. The blue path crosses the fence at y = b/2 and the red path crosses the fence at at y = b. Also note that by definition, we decompose the paths according to the LAST time they cross the fence i.e. at the maximum height at which they cross the fence.
Hence we can cross the fence at all units from y = 0 to y = b. This gives us disjoint and exhaustive subsets of paths. Total we get b + 1 subsets. This gets us closer to the summation in the LHS.
Now we need to look at the consequences of what we did. We placed the fence, and so we sort of “forced” the paths the superstitious guy can take. Once he crosses the fence he can only go East(can’t go North because we took the last height at which he crossed the fence) towards x = a and then proceed North towards y = b. And since the paths are fixed after x = a -1, we need to find the combinations of North and East steps BEFORE that. Essentially, we are travelling a-1 East steps and then j = 0,1,…,b steps get to that fence. Hence we have a total of (a - 1 + j) steps to cover and only a -1 of them can be East steps. So the total number of such paths is :
And summing over all j, we have,
And look what we have, it’s our old friend, the LHS!
I think the most important thing in these kind of problems is the intuition to know how we can compare normal algebraic expressions to something much more tangible. Hopefully, this was a good introduction. I’ll try to write more about the problems we solve in class and in homeworks. Working mostly on theoretical fields of Statistics and ML, I had forgotten all about how much fun numbers could be. It was what had initially led me to this field. But taking this course taught has reignited that interest in numbers. Hopefully, this blog series shall do the same for you!
References
- Professor Alexander Yong’s class notes and exercises, MATH 413 in Spring 19, UIUC. You can also check his website out.
- Brualdi, “Introductory Combinatorics” (5th ed)
