## Discrete Math 101: Fun with Combinatorics – 2

3. ${n \choose k} = {{n-1} \choose {k-1}) + {{n-1} \choose k}}$

Our task is to select a team of k players from among n players. Now, we have 2 options – Either select player 1 to be part of the team, or leave him out of the team.

If we select player 1 to be part of the team, our task is reduced to selecting $k-1$ players from among $n-1$ players.

And if player 1 is not part of the team, our task is reduced to selecting $k$ players from among $n$ players.

Hence we have the above result.

———

4. ${n \choose k} = {{n-1} \choose {k-1}} + {{n-2} \choose {k-1}} + { {n-3} \choose {k-1}} + \ldots.$

Again our task is to select a team of k players from among n players – $P_1, \ldots, P_n$.

If $P_1$ is part of the team: We can select such a team in ${{n-1} \choose {k-1}}$ ways.

If $P_1$ is not part of the team, and $P_2$ is part of the team: The problem is reduced to selecting k-1 players from among n-2 players.

If $P_1$ and $P_2$ are not in the team, and $P_3$ is in the team: The problem is reduced to that of selecting k-1 players from among n-3 players.

Proceeding in this manner, we get the above result.

———–

5. ${n \choose k} = \frac {n}{k} {{n-1} \choose {k-1}}$

Again, we have n players at our disposal from among whom we wish to select a team of k players.

Say we select $P_1$ to be the 1st player in our team. (Note that the term “first” actually means nothing since we wish to select a “set” of objects and not an “ordered list”. However the usage of such terminology is useful for the purposes of exposition.)

Now, all we need to do is to select $k-1$ players from among $n-1$ players.

Now, let’s go back a step. What if we select $P_2$ to be the 1st player of the team, and select the remaining players for the team in ${{n-1} \choose {k-1}}$ ways.

We can see that we have n choices for the 1st player of a team.

Hence, we can select a team of k players in $n \times {{n-1} \choose {k-1}}$.

But again some teams are being repeated.

Given a fixed team, say T, we select that team k times (with each of the k players in the team being selected as the 1st player of the team). Hence we need to divide the previous result by k.

Hence we get the above result.

———-

## Discrete Math 101 : Fun with Combinatorics -1

$n \choose k$ is the number of ways we can select k items from a group of n items. Say the number of players in India’s world cup squad is 14. Only 11 players can play in any particular match. Hence, on match-day, the coach has $14 \choose 11$ possibilities for selecting a team of 11 players from his squad. (Of course, such a situation is simply a theoretical conjecture, and no sane coach would actually list down each of $14 \choose 11$ possible teams and pick one from among them.)

We can easily derive some interesting results using the above meaning of $n \choose k$.

1. ${n \choose k} = { n \choose {n-k}}$

Our task is to select a team of k players from among n players. We can do this by directly selecting which players are to be part of the team, or by selecting which players are to be left out, giving the above result.

2. $n \choose k$ = $\frac { n! } {k! (n-k)! }$

Look at it this way. We have n players, say $P_1, \ldots, P_n$, and we want to select a team of k players from among them.

Let us select the players one by one.

For selecting the first player, we have n possible options.

Now having selected one player, we have n-1 possible options for selecting the 2nd player.

Similarly, given that we have selected i players, we have n-i options for selecting the i+1 th player.

Thus, we get that we can select k players from among n players in $n \times (n-1) \times (n-2) \times \ldots \times (n-k)$ ways.

But wait!

There are many repetitions in the teams of 11 players that we selected. Consider any particular fixed team of k players. That team is selected by us in $k!$ ways.

Therefore, we have: ${n \choose k} = \frac {n \times \ldots \times (n-k)} {k!} = \frac {n!} {k! (n-k)!}$.

——-

Note that given a list of k items, we can have k! permutations of those items. (This can be easily derived recursively.)

——-

## Probability – Monty Hall problem

Our friend Monty Hall is a game show host. Every week he asks one person from his audience to come onto the stage. On the stage are 3 closed doors. Behind one is a brand new car, and behind the other 2 are goats. The car is equally likely to be behind any of the 3 doors. The contestant selected from the audience obviously wants to win the car.

Monty Hall explains the rules of the game to the contestant — In front of you are 3 closed doors. Behind one of them is a car, and there are goats behind the other 2. I know what is behind each door. Your first task is to select a door.

Our contestant selects door 1.

—-

Monty now again starts expounding on probability — You have selected door 1. Now, I will select either door 2 or 3 to open. Note that I know what is behind each of the doors. I will decide which door to open based on the following rules:

– If door 2 has a car behind it, I will open door 3.

– If door 3 has a car behind it, I will open door 2.

– If neither of the above conditions hold true, i.e. both doors 2 and 3 have goats behind them, I will randomly select one among these 2 doors with probability 0.5 and open that door.

—-

Now, having explained thus to our contestant, the omniscient Monty goes and opens door 3, and reveals to the world (including our contestant) the goat standing behind it.

—-

Now, Monty turns to the contestant for the endgame and speaks thus — As you can can see, door 3 has a goat behind it. Doors 1 and 2 are still closed. Whichever door you select, you will get whatever is behind that door. You can either decide to stay with your original choice i.e. door 1, or you could decide to switch i.e. select door 2. What do you want to do — stay or switch?

As the music in the recording studio rises to a crescendo, our dear contestant is faced with this question on probability to answer. What should he do?

————

At first glance, it does seem that it is immaterial as to what the contestant chooses. One could argue that there are 2 doors (doors 1 and 2) one of them having a goat behind it, and the other having a car behind it. The car is equally likely to be behind either of the 2 doors. So, the contestant could as well flip a fair coin, and choose which door he wants to go with.

—-

However there is a flaw in the above reasoning.

— The probability that there is a goat behind door 1 is 2/3, and the probability that there is a car behind door 1 is 1/3.

To see why this is so, consider the following argument — Initially there were 3 doors. Two of them had goats behind them and one of them had a car behind it. Door 1 was one among these 3 doors. Therefore, the probability that door 1 has a car behind it is 1/3 and the probability that it has a goat behind it is 2/3.

Now, you could argue against the above explanation this way : ” What you said about the probability of a car being behind door 1 being 1/3, and that probability of a goat being behind door 1 being 2/3 was true initially, and not after Monty went and opened door 3, and showed everyone the goat standing behind it. Once Monty did that, we were left with 2 doors, and 1 goat and 1 car, and hence the probability that there is a car behind door 1 is 1/2 and the probability that there is a goat behind door 1 is also 1/2.”

But again, the argument that you presented above is not wholly correct. We can see it this way — we agree that initially i.e. before Monty opened door 3 and showed a goat behind that, the probability of these being a car behind door 1 is 1/3. My claim is that this remains the same even after what Monty did.

To better understand that, consider the following situation —

Assume that there are 100,000 doors instead of just 3. Also, behind 99,999 of these doors are goats and behind a single one is a car. The car is equally likely to be behind any of the 100,000 doors. So, what we have here is a 100,000-door version of Monty’s 3-door problem.

Now, you select a door, say door 385.

Now, Monty has been asked to open 99,998 doors, i.e. he has been asked to keep 2 doors closed. It is also specified in the rules that one of these closed doors should be door 385 since that was the one you selected. Further, Monty knows what is behind each of the doors, and Monty has been specifically instructed that the 99,998 doors that he opens should all reveal goats behind them.

So Monty goes and opens 99,998 doors. He leaves door 385 and one other door, say door 6724 closed. Now, as we said earlier, behind each of the 99,998 doors that Monty opened, was a goat.

Now, what do you think is the probability that there is a goat behind your selection door 385?

It is 1/100,000 and not 1/2.

The reason as to why door 385 remained closed even when just 2 doors remained (i.e. 385 and 6724) was because Monty had been instructed not to open 385 as part of the rules.

There is 1/100,000 probability that door 385 contained a car behind it, and Monty selected door 6724 uniformly at random from the remaining 99,999 doors for keeping closed. In such a situation, staying with your original selection (i.e. door 385) would win you the car.

However, it is much much more likely (99,999/100,000) that your initial selection (385) had a goat behind it, and that Monty knowing that 6724 had a car behind it, opened the remaining 99,998 doors. In this situation, switching (i.e. selecting door 6724) would get you the car.

—-

Coming back to our 3 door version, we can argue that switching would win you the car with probability 2/3, while staying with your original selection would get you the car with a probability of 1/3.

Hence, one who has a working knowledge of probability should advise the contestant to switch.

## Greed, and love of dear life: The Pirate Problem

There are $n$ pirates discussing on how to divide their booty of 100 gold coins. The pirates have a strictly defined seniority order among themselves. Let’s say that, for all i, Pirate i is more senior than Pirate j, for all j < i.The method that they agree upon to divide their loot is the following:-

—-

Initially there are n pirates.

i = n;

While (there is a pirate alive)

Pirate i proposes a division.

If (at least 50% of the pirates alive approve of his division plan)

Division takes place, and things end here.

Else

Pirate is killed (and of course, the division proposed by him is not carried out).

i – -;

End of While loop.

End of algorithm.

We also have a few other observations to make:

1. The pirates value their own individual lives most of all.
2. Next to protecting their lives, the thing uppermost on their minds is to maximize their own share of the loot.
3. The 3rd most important consideration for the pirates is to reduce the number of pirates on board.
4. All pirates are extremely intelligent (and thus, each certainly knows that, each of the others is extremely intelligent).
5. Whenever pirates have to make a decision (whether to approve/ disapprove of, or to propose a division plan), they keep in their minds the 4 points mentioned above.

Question: Say, n = 5, what division should the senior-most pirate propose (he is the one who gets the first chance to propose a division plan) so as to ensure that he doesn’t get killed, and given that he doesn’t get killed, to maximize his share of the loot?

Solution.

Consider what would happen with just one pirate. Obviously, he would get all the 100 coins.

With 2 pirates, Pirate 2 gets to propose a division. He knows that he will always get 50% of the vote (by approving of his own plan), and hence can propose freely any division that he likes. Hence, he will propose a division with 100 coins for himself, and none for Pirate 1, and get away with it.

With 3 pirates, Pirate 3 has to decide on how to divide the loot. He knows that if he dies, only 2 pirates would be left. In such a scenario, we all know that Pirate 1 will not get any coin. Hence, Pirate 1, being greedy, has an incentive to accept any plan that Pirate 3 proposes giving him > 0 gold coins so as to ensure that Pirate 3’s division plan is carried out. Hence, Pirate 3 can win 2 votes (out of 3) by proposing a division giving 1 coin to Pirate 1 and keeping 99 for himself.

With 4 pirates, Pirate 4 gets to decide the division scheme. Again, we know that, if Pirate 4 dies, Pirate 2 wouldn’t get even one gold coin, in the subsequent division which would be proposed by Pirate 3. Hence, Pirate 4 can win 2 votes (out of 4) by proposing a division giving 1 coin to Pirate 2, and keeping 99 for himself.

With 5 pirates, it is Pirate 5 who gets to propose. Again, his death would result in Pirate 1 and Pirate 3 not getting anything in the subsequent division which would be proposed by Pirate 4. Hence, to win their votes, and get 3 votes (out of 5), Pirate 5 can give 1 coin each to Pirates 1 and 3, and keep 98 for himself.

—-

Generalizing for n (n < 100):-

Pirate n can propose a division giving 1 coin each to Pirates n-1, n-3, … (up to either 1 or 2), and keep the rest for himself.

—-

## A beautiful proof

There are some proofs, for which the very fact of being acquainted with the working of the mind which came up with such beautiful ideas can transport you to a state of ecstasy.

Georg Cantor (1845-1918) gave a beautifully simple proof for proving that the power set of the set of natural numbers (N) has “more” elements than the set N itself, i.e. 2^N is uncountably infinite.

Assume to the contrary that 2^N is countably infinite. In other words, there exists a bijection between the set N and the set 2^N. (This is what is meant by a set S being countably infinite, i.e. if a set S is countably infinite, then there exists a bijection between S and the set, N of natural numbers.)

2^N = {R_0, R_1, R_2, … }  [R_0, R_1 etc are elements of 2^N i.e. subsets of N.]

Assuming that 2^N is countably infinite implies that every element of 2^N is equal to R_i for some i \in N.

Now, consider this set. Call it D.

If  0 \in R_0, then 0 \notin D.
Else if, 0 \notin R_0, then 0 \in D.

Similarly, deciding whether or not each i \in N belongs to D, is done based on whether or not i belongs to R_i.

If R_i contains i, then we do not include i in D.

And if R_i does not contain i, then we include i in D.

What do we get now?

We get a set D that is different from each R_i. (It is different from R_5 in whether or not ‘5’ is contained in it; it is different from R_345 in whether or not ‘345’ is contained in it. Hence, D can not be equal to set R_5. And, D can not be equal to set R_345.)

So, we see that D can not be equal to any of the sets R_i.

But, D is also a subset of N.

Hence, D should ideally be an element of the power set of N. By assumption, 2^N = {R_i : i \in N}.

We just saw that D can not be equal to any R_i.

Hence D is NOT a part of 2^N.

We are done. 2^N can not have a bijection with N. 2^N is uncountably infinite.

## Extended Longest Path problem

These are slides from a talk on the Longest Path Problem at the Penn State Theory seminar.

Talk_longest path

In the Longest Path Problem, we are given an undirected graph, G =(V,E), and integer $k \geq 0$, and are asked to find out whether or not there exists a simple path of length k in G.

The Extended Longest Path Problem is a variant of the above. Here, we are asked to find out all pairs of vertices that have a simple path of length k between them.

## Longest Path: Method of Random Orientations

In this post, we shall consider an NP-complete problem, namely that of determining whether a simple path of length k exists in a given graph, G = (V,E).

Formally,

LONGEST PATH PROBLEM

Input: undirected graph, G = (V,E), integer $k \geq 0$.

Parameter: k

To find: Does G contain a simple path of length, k?