Difference between revisions of "Committee forming"
(categories) |
|||
Line 1: | Line 1: | ||
+ | {{WotWAnnounce|week=September 5- September 11}} | ||
+ | |||
'''Committee forming''' is one technique for solving certain [[combinatorics]] problems. | '''Committee forming''' is one technique for solving certain [[combinatorics]] problems. | ||
Revision as of 17:53, 6 September 2008
This is an AoPSWiki Word of the Week for September 5- September 11 |
Committee forming is one technique for solving certain combinatorics problems.
Contents
Introduction
First, we'll introduce committee forming with a simple example.
Problem
How many committees of 3 people can be formed from a group of 12 people?
Solution
Suppose that the order in which we choose the members of the committee didn't matter. Then there would be 12 possibilities for the first person, 11 for the second person, and 10 for the last person. So by the multiplication principle there would be total committees.
However, the order we choose them does not matter. So we have overcounted. Since there are ways in which each distinct committee could have been chosen, we divide our result by 6 to get
.
Note: there is a special notation for expressing the number of ways to choose a committee of size from a set of size
. We use
which is called a binomial coefficient. From here on in this article, we will use this notation.
Proving Combinatorial Identities
The committee forming method can be a very powerful tool for proving combinatorial identities.
Problem
Prove that
![${n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose n} = 2^n.$](http://latex.artofproblemsolving.com/a/3/a/a3a0dd3bec9d72eba50d8a6c1d1f828a8baa9c2a.png)
Solution
We can look at each term individually: is the number of ways that a committee of size 0 can be chosen,
is the number of ways that a committee of size 1 can be chosen, and so on. Thus, the problem can be recast as finding the number of committees of any size that can be formed from a group of
people. Each person can either be in the committee or not in the committee. Since there are two possibilities for each person and each person is independent of every other person, there are
committees.
Further Problems
Introductory Problems
- Find the number of ways to choose a committee of size 4 from a group of 8 people.
- How many ways can a committee of size 3 be chosen from a group of 10 people if one of the 3 people on the committee is designated as the president?
- Compute the value of
.
Intermediate Problems
- Three slips of paper are dropped in a hat. The numbers 1, 3, and 9 are written on them, respectively. Any number of slips are pulled from the hat and the numbers written on them are added together. How many different sums are possible?
- Prove that
.
- Prove Pascal's identity:
- Prove that