Archive for the ‘Combinatorics’ Category

Yesterday in Pre-Calculus class we were discussing combinatorics and came across a series of questions on how many ways can a best 2 out of 3 sets tennis match be won and how many ways can a best 3 out of 5 tennis match be won.

For a 2 out of 3 scenario there are six possibilities (AA, ABA, BAA, BB, BAB, ABB) and for the 3 out of 5 scenario there are 20 possibilities (AAA, BAAA, ABAA, AABA, BBAAA, BABAA, BAABA, ABBAA, ABABA, AABBA and ten more in which B wins).

The question then came up of how to generalize these results.  The way I approached this was to consider how many ways one of the players could win and then double the answer to include the scenarios in which the other won.

One of the issues in this type of problem is that once the winner has won the required number of games the match ends, so that a best 2 out of 3 match could never end AAB, for instance.  Another issue is that each of the possibilities of winning in a different number of sets should be considered separately.  That is, winning in the minimum number of sets, then winning after having lost one set and so forth.

Taking all of these issues into account for a competition in which the winner must win \frac{n+1}{2} out of n leads to a general formula of 2*\displaystyle \sum_{k=0}^{\frac{n-1}{2}}{_\frac{n+2k-1}{2}}C_{k}.

Or – if the winner must win g out of 2g-1 then the formula would be 2*\displaystyle \sum_{k=0}^{g-1}{_{g+k-1}}C_{k}.


Read Full Post »


We were covering some elementary combinatorics in the Pre-Calculus course this past week and were discussing some problems from VK Balakrishnan’s Discrete Mathematics textbook.  I took a Discrete Math course at University of Maine in 2000 from Balakrishnan and really enjoyed the class.

I needed to make a quiz question for the Pre-Calculus class and tried to remember some of the more interesting ways Balakrishnan had constructed his problems and came up with this one:

Seven people (A, B, C, D, E, F, G) want to ride into Portland but the car will only hold four.  Person “A” owns the car and will always be driving.  People “F” and “G” don’t get along and won’t ride together.  If it makes no difference where in the car people sit, how many ways are there for four people to ride into Portland together?


Read Full Post »