Combinatorics with Blitzstein and Hwang

Also from Blitzstein and Hwang, seven chess matches are played between players A and B.  How many ways can the final result be 4-3 to A?

In doing this question, I am reminded about how almost all of the difficult work in maths questions comes in unpacking the question.  This unpacking is also the act of modelling.  And it isn't easy when you're doing it from scratch.

So my initial thinking was to transform the problem into a counting problem.  We don't need to model B at all here - it can all be done in modelling how A gets those 4 points.  This is because each game has precisely one point to distribute, and that will certainly happen at the end of each game.  So B disappears from the analysis.  This is like the 'degrees of freedom' idea in statistics 

With only seven games, there's no way A could have finished with 4 points without at least one clear victory.  At the other end of chess playing competence is the possibility that A won 4 (and therefore lost 3).  Note also that the number of draws must always be 0 or some multiple of 2.

Now that B has been dispatched, we look at the triplet which is a result.  In general, there are the following four ways that 4-3 can result, were W=A win, D=draw, L=A loss:

• 1W 6D 0L
• 2W 4D 1L
• 3W 2D 2L
• 4W 0D 3L

Now we can use the 'degrees of freedom' trick one more time.  If you know two elements of this triplet, then you'll know for sure what the third element is.  So we don't need to model three distinct values for D,W and L. We only need two, but which two?

I always prefer to go for smaller numbers, and on that basis, I'd go for W + L.  We shall henceforth model only A's wins and losses, since A's draws are implied.

Now we have a sum of 4 possibilities.  Let's take them one by one. ${7} \choose {1}$  represents all 7 locations where that one win would happen.  We don't have losses since by implication all the six other slots were draws.  So for this sub-case, we're done.  Once we place the  win, we have no more variations to deal with.

  ${{7} \choose {2}} { {5} \choose {1}}$ represents first how we can distribute two wins among the seven games, then when that's done we have 5 unfilled slots which we need to drop one loss into.  We multiply those two together (choices multiply).

Similarly,   ${{7} \choose {3}} { {4} \choose {2}}$ represents 3W + 2L.  And finally   ${{7} \choose {4}} { {3} \choose {3}}$ represents the case where we drop in four wins, then all remaining slots contain the full set of 3 losses.

The final answer to the question is: ${{7} \choose {1}} + {{7} \choose {2}} { {5} \choose {1}}  + {{7} \choose {3}} { {4} \choose {2}} + {{7} \choose {4}} { {3} \choose {3}}$

R thinks this amounts to 357 different possible ways to arrive at a 4-3 result for A.

MISSISSIPPI scramble

How many ways are there, Blitzstein and Hwang ask, to permute the word Mississippi?  There are two approaches.  Broadly, we're in the 'naive probability' world where all possibilities are equally likely, so counting methods are going to be useful.

First, and this is generally a good strategy, we give all 11 letters a unique identity.  That is to say, the first s must be thought of as distinct to the second, third and fourth, and so on.  This is analogous to understanding that when you throw a pair of dice, logically there's always a first and second identity for each die. 

There are $11!$ ways (39,916,800) to permute the 11 'distinct' letters (multiplication rule, based on sampling without replacement).  That's more ways than there are actual people currently residing in Mississippi:

Looks like it would take another 500 years, at the current rate of population growth, before we'd run out of basic ways of sharing all the permutations of Mississippi with its inhabitants.

But at this point we want to throw away (divide out) certain permutations.  From a schoolteacher point of view, wherever those four s's landed up, we don't care about their particular order now.  In other words, we're making the conscious decision to consider an s like any other s.  And an i like any other i.  And a p like any other p.  A kind of homogenisation.  The m stands unique and proud at the head of the word.  But in terms of permutations, the m is the unmodelled case, since, when you've decided how to fill the 10 other slots using all your s's, i's and p's, then the m just has to go where it is told.  What a come down - tables turned on the m.

There are four s's, and four i's.  And we need to know how much not to care about their order.  If we did care for their order, then we could permute them $4!$ ways.  Similarly there are $2!$ orderings of p.  So we want to throw away in total  $4!4!2!$ of the $11!$, meaning that the 'schoolteacher's answer' (were all letters are considered homogeneous) is $\frac{11!}{4!4!2!}$.

The second solution is to break it down into 3 sections, each with a binomial 'n chose k' element.

Let's start with the s.  We have 11 slots and 4 of them.  So $11 \choose 4$.  Using the multiplication rule, you then could drop your 4 i's into any of the remaining 7 slots, $7 \choose 4$ and finally our two p's can take up any of the three remaining slots, $3 \choose 2$.  Again, m is the unmodelled, bossed about letter who must take the last slot, wherever that is.  

So,  it must be the case that $11!/4!4!2! = {11 \choose 4}{7 \choose 4}{3 \choose 2}$.

What does R have to say about that?

It agrees, and gives us the final (schoolteacher's) answer, 34,650 versus the 'radical identity' answer of 39,916,800.

So perhaps we could give the school teacher permutations just to the Hispanic residents (excluding Puerto Ricans, sorry).