The Art of Counting: Part II

Last week, we covered three examples of theorems that we needed to prove and solved them by comparing them to real-life problems. This week, we shall continue from there. As a side note, we will not be using any algebra again, this article series aims to cover combinatorial proofs without any complex notations or equations. You can refer to the textbook mentioned at the end for a much more mathematical analysis.

We’ll start with a very simple identity to prove and then cover the concept of distinguishable objects.

Example 1: The General and his Dinner Plans

Prove:

Imagine you’re a General and you have two battalions having n male soldiers and n female soldiers. Your opponents are far away and it’s nighttime and so you want to send 2 soldiers out to get firewood so you can cook. How many possible ways are there to do that?

Recognize that the LHS of the equation above is asking just that. So now we have to formulate the RHS thinking about the number of ways we can choose the 2 soldiers from both the battalions combined.

One way could be that we choose 1 male soldier and 1 female soldier (Equality rules!), which means we have n choices for the male soldier and n choices for the female soldier. So we get..

And we’re one term closer to our RHS. Now, you are impartial between the two genders, and you can either choose two men or two women soldiers as well. So that means we can choose the 2 soldiers from either of the group having n soldiers each.

And so we basically have covered all our bases and have no other choices apart from these. And since these are mutually exclusive, we can simply add them to get the total number of ways you can choose the 2 soldiers to get the firewood. And the sum comes out to be..

There. Done. The key factor here is to recognize that

And then remember that whenever we have a sum on top, we can easily work on groups. This was a warm-up from last time. We can now move on to greener pastures.

Example 2: Fill in the Blanks

Prove that the number of permutations of m A’s and at most n B’s equals

[Brualdi , 5th ed, section 2.7: Q48]

And with this example, we also introduce another category of combinatorial problems — the string based problems.

The trick in these type of problems is to look at the term in the denominator — m + 1 and then also note that this term is also there on the top. So basically we’re looking to choose m + 1 objects out of a group containing n objects of some other type.

So the problem says this — we take m A’s and some number of B’s (can be 0,1,2, …n) and permute them. By permuting them, we are actually choosing the places where A’s can go, the rest of them will automatically take A’s. So we can write this as a summation:

To make what we’re doing clearer, let’s take an example. Let m = 3 and let the length of the string we’re building be 8. So in this case we can have :

The blank spaces all take A.

However let’s say our n = 3. That means number of B’s can be 0, 1, 2 or 3. So total we can have a string of length 3, 4, 5 or 6 respectively.

Now that it’s clear what we’re doing, we can have a look at our RHS, which basically gives us a way to choose m + 1 objects out of m + n + 1 objects. Okay, so let’s assume we now have m + n + 1 total blanks and we need to fill m + 1 of them with A’s. This may seem confusing right now, because in LHS, we took exactly m A’s, but just hear me out.

The last position in our string where we can get A can go from m +1 -th blank, to m + n + 1 -th blank, because we have m + 1 A’s and we have maximum m + n + 1 blanks. By last position, I mean :

Let this last position of A be represented by the index j (see how we’re inching closer towards the LHS?)

Now, we count.

When we have j = m + 1, we have the following case:

We can choose the m A’s before the last A from the remaining j-1 (= m) blanks left before that, which is:

OR we have j = m + 2, which means something like this:

So we can choose the remaining m A’s to fill the blanks before the last A — which are m + 1 in number:

Aha! We’re close. Can you see it? Now we just extrapolate. The last position can take values like m + 3, m + 4 …m + n + 1 and we always have m remaining A’s to place before the last A:

And once we sum them up, we get:

And QED.

This has been a sort of different proof, so we summarize:

1. First we represented the LHS as a sum.
2. Then we took the RHS and twisted it, so we could represent it as a sum too — and counted the same set in two different ways.
3. Then we equated both the sums.

Now, let’s briefly introduce the concept of indistinguishable objects and combinations with repetitions.

Example 3: Dunkin’ Donuts!

Often, in real-world applications, we see that not all objects are unique — hoodies, cups, chairs, doughnuts etc. We have many different types and a certain number of the objects of the same type. But we often need to know the total number of ways to arrange these things in a store or in Dunkin’ Donuts.

Prove: Show that the number of ways of selecting r things from k objects with repetition is :

Okay, now we have k unique objects and we have to choose r things from a set containing unlimited things of each object type. Let’s take an example. Let’s go to Dunkin’ Donuts.

And say we have these 4 types of doughnuts available:

1. Glazed
2. Old-fashioned
3. Jelly
4. Chocolate Frosted

Now let’s say we decide to bring a box of dozen donuts home and we only have the 4 types available in our store, but unlimited of those 4 types. We can either get all 12 of Chocolate Glazed (let’s be honest, it’s the best.) or I could get 4 Chocolate Glazed, 2 Glazed, 3 Old-fashioned and 3 of the Jelly ones. We have unlimited (not really, LOL) choices.

And so basically what we can do is represent all the donuts with O’s and we partition our box with |. So we between one bar and the next, we have all donuts of the same type.

So our box looks like this:

We can place the partition i.e. the bars anywhere between the 12 donuts. And so this problem can basically be transformed to a problem of permuting the symbols — O’s and |’s and since we have 4 types, we have 4–1 = 3 bars and 12 things that we want to choose. So how many sequences of O’s and |’s do we have?

We have k-1 bars and r O’s and so we have a total of r + k -1 symbols and we need to find where to place the the O’s i.e. just like the fill in the blank problem above, we need to fill the blanks with O’s or |’s and so we choose the blanks where the O’s i.e. the donuts will be placed and the rest of the blanks will automatically have |’s.

The number of ways this can be done is:

And we get our RHS!

Hopefully, this was a simple intro to how to solve combinatorial problems the non-algebraic style and these are actually called combinatorial proofs.

In the next part, we’ll cover more examples on this and then also introduce the pigeonhole principle.

And if you haven’t already, do check the first part out here!

References:

1. Professor Alexander Yong’s class notes and exercises, MATH 413 in Spring 19, UIUC. You can also check his website out.
2. Brualdi, “Introductory Combinatorics” (5th ed)
3. https://math.stackexchange.com/questions/357063/proving-that-sum-limits-k-0n-mk-choosem-mn1-choose-m1