More Bijections!

Posted on by

You can imagine that I’m really bored as I’m writing another blog post given I just wrote one yesterday. Anyhow, some more identities, with some more proofs. This post will be one of the most brusque posts I’ve ever written; so yes, you can blame me if you can’t understand parts of the post. (Yes, you may comment and I’ll respond, I promise.)

Behold!

\displaystyle \sum_{i=0}^{n} \dbinom{x}{i} \dbinom{y}{n-i} = \dbinom{x+y}{n}

Assume there is a class of x boys and y girls. (No, you may not assume x = y and that every girl/boy has a boy/girlfriend.) Now, you’re to pick n out of the class to go for a movie. The right hand side simply counts the number as a binomial coefficient without distinguishing between boys and girls. The left hand side, being a sexist, distinguishes between boys and girls, and picks i boys first, and then n-i girls for the picnic. Using the addition principle, the left hand side (sexist sod) counts the number of ways to take a total of n boys and girls for the movie.

Now that you’re bored watching the stupid movie, why not try another combinatorial identity? Yes, this one is a bit tricky. I always like the tricky ones.

\displaystyle \sum_{i=0}^{m} \dbinom{n+i}{i} = \dbinom{n+m+1}{m}

Consider the scenario where you have n +m+1 girls standing in a queue (or a stack or even a list). You are to pick, well, m girls out of the given n+m+1 for another movie this time. Again, the right hand side is the straightforward answer. The left hand side counts the same quantity, evaluated in a slightly complex way. We look at the largest continuous set of girls we’ve selecting starting from the first one. We can select at most m in this continuous string, or none at all. We select the first m-i (note 0 \le i \le m) girls, skip the (m-i+1)^{\mathrm{th}} girl (as we select the longest continuous string), and select the remaining i girls from the remaining n + m + 1 - (m - i) - 1 = n + i (removing the selected the first m-i, and rejected (m-i+1)^{\mathrm{th}} girl). Applying the addition principle on this evaluation simply yields the result.

Football! (And we need a captain this time.)

\displaystyle \sum_{i=0}^{n} i \dbinom{n}{i} = n2^{n-1}

This is one of my favourite identities among those which have a very simple bijective proof. Consider selecting a football team out of n boys with a captain. One way to count the number of possible teams is to select an arbitrarily sized team, and then select the captain out of the chosen ones. The left hand side simply counts this number. Another way to evaluate the same number would be to select the captain first, which can be done in n ways, and then select the remaining team, which can be done in 2^{n-1} ways (as you may either select a player, or reject him). And voila!

Boom! (Just wanted to end this post with a blast.)

PS The promised exercise for my devout readers is to prove the following identity.

\displaystyle \sum_{i=0}^{n} i^2 \dbinom{n}{i} = n(n+1)2^{n-2}

PPS You might want a goalkeeper on your team to save a goal from the identity above.

Bijections!

Posted on by

Hello, imaginary reader! Long time, no see. It’s okay, I prefer rooks anyway. Now that I’ve started with a lame unoriginal joke you probably didn’t understand, I can continue with the core matter of this post which I’ve wanted to do for a long long (exponential) time. Proving combinatorial identities with bijections! This post is going to be somewhat terse, as that is the point of proving an identity bijectively.

I presume one knows what binomial coefficients mean bijectively, and some basic combinatorial principles like addition and multiplication principle. I’ll be a bit more explanative in the starting few examples, after which I’ll just, well, be lazy and write a few words which should be enough, given sufficient time, for one to understand.

So, here goes.

\displaystyle \sum_{i=0}^{n} \dbinom{n}{i} = 2^n

The left side counts the subsets of size i of a set of size n where i ranges from 0 to n. In particular, the left counts all the subsets of the set in reference by addition principle; whereas the right side counts all the subsets of the set in reference by multiplication principle, as each element of the set has 2 choices, either to be included in a subset, or not.

Moving on.

\displaystyle \sum_{i=0}^{n} (-1)^n \dbinom{n}{i} = 0

Okay, I’ll cheat a bit here. I won’t directly equate the left and right sides of the above identity, but make the “clever” and obvious observation that it is equivalent to proving that the number of odd sized subsets of a set, and the number of even sized subsets of a set are equal. The proof is surprisingly simple. Fix any arbitrary element a from the set, and any arbitrary subset A of the given set. If A contains a, remove a from A to get a new set A' of the opposite parity. If A does not contain a, then add a to A to get a new set A' of the opposite parity. I’ll leave it to you to verify that this gives a bijection between subsets of a set with even parity and subsets of a set with odd parity.

Simple enough.

\displaystyle \dbinom{n-1}{i} + \dbinom{n-1}{i-1} = \dbinom{n}{i}

Let’s play football now! The right hand side simply counts the ways of choosing i players from a total of n for the starting squad. Now, for the left hand side, fix an arbitrary player p. If you pick p, then you’re left with n-1 players and have to pick i-1 out of them. On the other hand, if you don’t pick p, you’re left with n-1 players, and have to pick i out of them. The sum of these two, is the left hand side, and by the addition principle, equal to the number of ways of choosing i players from n, the right hand side, as desired.

And we’re done.

As you know the number of lazy bones I have is 207, I’ll stop right here.

Anyhow, I plan to convert this post into a series of posts on bijective identities, with three identities with bijective proofs, and one identity to be left to be proven by the lovely imaginary readers of my blog. Happy solving!

\displaystyle 2 \dbinom{2n-1}{n} = \dbinom{2n}{n}

Object Copier

Posted on by

Rijul Saini recently handed me a hypothetical scenario equivalent to the following:

Consider two boxes, A and B, each with a door, such that when both the doors of A and B are closed, the contents of A are destroyed, and are replaced by an exact copy of that of B.

Rijul was obviously stuck with considering the applications these boxes could have in real life, unlike me, who always desires to create a paradox, or in the worst case, a strange loop. The motive of this post is to argue against the exist of such boxes even in a (logical) hypothetical world. # All logical worlds are hypothetical.

Firstly, since the contents of B are reproduced in A, A has to be as large as B.

Now assuming that B can fit inside A, we fit B (with a chocolate inside it perhaps) inside A. We close B’s door, and A’s door. Now, the contents of A are (specifically, box B is) destroyed and replaced by the contents of B. But is it really a contradiction? What are the contents of the destroyed box B? One might argue that we’ll just find A empty in the end for box B is destroyed, and there are no contents of box B but void. But the problem with that is that box A calls box B to copy B’s contents to itself. Since box B no longer exists, it’s error 404. Since box B no longer exists, A loses it’s property of being able to copy whatever is present in B for B no longer exists.

To sum it up, if one can fit B inside A, it is possible to reach a paradox. One might argue that the paradox is not intrinsic but rather artificial; but I’d like to point out that most of the paradoxes are created, and emerge solely because the appropriate situation which results in them is thought of, or possibly constructed.

The other case, when one can’t fit B inside A, is far more tedious. Apparently, it’s so tedious that I haven’t been able to come up with a paradox, yet, which would eventually destroy the system and give me immense sadistic pleasure. Nevertheless, I trust that this scenario is much harder to deal with for it’s not immediate that we can call the system on itself like in the previous case by fitting in box B in box A. For now, I’m quite rather unsure whether the system of such boxes will be possible or not, but a paradox eludes my imagination for now.

PS This is a purely recreational blog post supposed to make no sense whatsoever. In the rare event that you find this article sensible, I suggest you book an appointment with your psychiatrist, for the subtle fact that you find this sensible, implies the existence of one.

On a Puzzling Chocolate Bar…

Posted on by

I know I haven’t posted in a while and you all have been mad at me for that. But I know you all are very kind and patient and have been waiting for my next post. And to reward you for your sincerity and probity, I’ll discuss about something we all totally love, chocolate bars.

So, let’s begin with a chocolate bar… and make more out of them. # Yes, I’m gonna share it with you.

You have a regular chocolate bar marked into m x n squares, and you wish to break up the bar into its constituent squares. At each step, you may pick up one piece and break it along any of it’s marked vertical or horizontal lines. Prove that every method finishes in the same number of steps.

I handed this puzzle to several of my friends. After a few minutes, most of them were convinced that (strong) induction was the way to go. But the problem automatically with “obvious” induction was that if one chose to induct on the length, an initial horizontal breaks ruins the dominoes falling down; and inducting of the breadth resulted in the same fall of “fall of dominoes”.

# If you’re not aware of induction, I’ve mentioned a much simpler solution in the last line.

Not many people think beyond the “obvious” variables to induct on. It’s the way we’re taught induction in school. Mostly we’re just given one variable, and a property P, and inducting on the variable to show that the property P is invariant is child’s play. But induction is much “stronger”.

So, following the discussion above, we note that we should be able to induct on a variable which incorporates both the length and the breadth, and decreases after each break. The “obvious” choice now is the sum of the length and breadth.

Now, let me fill in the gaps. We let f(l, b) (= lb – 1) denote the number of breaks required for an l x b chocolate bar. Now, assume that this result holds true for all chocolate bars with the sum of their length and breath being less than m + n. This is our inductive hypothesis. I’ll leave the base case as an exercise.

Now, if our original bar is broken vertically with one length being p and the other m – p, we have the number of steps equal to f(p, n) + f(m – p, n) + 1. Or, if the bar is broken horizontally, with one breadth being q, the other n – q, we have the total number of steps required being f(m, q) + f(m, n – q) + 1. (Note the 1 is added to both because of the initial break.)

Now, it all falls into place with our initial guess of f(l, b) (= lb – 1). Now the question arises where did it pop into place from? I’ll leave that to you too, or maybe you can just see that it is the obvious guess to the recursive relation we’ll obtain assuming the problem is correct.

Another solution, which is simpler in nature, is obtained by considering the number of pieces at each stage. After we break the chocolate once, the number of pieces just goes up by one. And voila, we’re done. # And so am I.