Feeds:
Posts

## Combinatorics

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?

I thought of three different ways to solve this – but the third way is inadvisable without having done the other two.

# Solution #1

First we can consider how many trips there are in which F and G would be riding together and subtract that from the total number of possible four person groups.  So, for the total number of trips, with A always driving we’re really choosing three people from the other six.  Since it doesn’t matter where they sit, this is:

$C(6, 3)=\frac{6!}{3!3!}=20$

The number of trips in which F and G ride together is small since A is always driving.  That puts three people in the car and we  must choose one of the remaining four to fill the last seat, so there are four ways to do this.  Twenty minus four is sixteen.

# Solution #2

We can also consider the trips in which neither F nor G ride, the trips in which F rides and G doesn’t and the trips in which G rides and F doesn’t.

The trips in which neither F nor G ride means we choose three of the remaining four people (B, C, D, and E):

$C(4, 3)=\frac{4!}{3!1!}=4$

Then the trips in which F rides and G doesn’t means we choose two people to ride (A and F) and must fill the other seats with two choices from the remaining four (B, C, D, E):

$C(4, 2)=\frac{4!}{2!2!}=6$

This is exactly the same for the trips in which G rides and F doesn’t:

$C(4, 2)=\frac{4!}{2!2!}=6$

So that makes 4+6+6=16.

# Solution #3

The last method is enumeration:

ABCD ABCE ABCF ABCG ABDE ABDF ABDG ABEF ABEG ACDE ACDF ACDG ACEF ACEG ADEF ADEG

The things I like about this problem are (a) it can be solved by subtraction  (b) since the possible scenarios are relatively few, they can added together and (c) the final answer is small enough that enumeration is not out of the question!