Is Fred on the committee?

I was just helping a student with his AoPS homework, when I came across the following related problems:

Eight people, including Fred, are in a club.  They decide to form a 3 person committee.  How many possible committees can be formed?

So we are choosing 3 people out of 8 or {8 \choose 3}.

How many possible committees include Fred?

Since Fred is taking one committee seat, that means we need to choose 2 more people from the remaining seven, or {7 \choose 2}.

How many possible committees do not include Fred?

Since we can’t choose Fred, we need to choose 3 members from the remaining 7 or {7 \choose 3}.

Since the total number of committees is equal to the number of of committees with Fred plus the number of committees without Fred, then we can say

{8 \choose 3} =  {7 \choose 2} +{7 \choose 3}.

Generally we call this Pascal’s Rule: {n \choose k} =  {n-1 \choose k-1} +{n-1 \choose k}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s