Difference between revisions of "Committee forming"
m (→Problem) |
m (→Problem) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 5: | Line 5: | ||
=== Problem === | === Problem === | ||
| − | How many committees of 3 people can be formed from a group of 12 people | + | How many committees of 3 people can be formed from a group of 12 people? |
=== Solution === | === Solution === | ||
| Line 18: | Line 18: | ||
=== Problem === | === Problem === | ||
| − | Prove that <center><math>{n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose n} = | + | Prove that <center><math>{n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose n} = 2^n.</math></center> |
=== Solution === | === Solution === | ||
| − | We can look at each term individually: <math>{n\choose 0}</math> is the number of ways that a committee of size 0 can be chosen, <math>{n\choose 1}</math> is the number of ways that a committee of size 1 can be chosen, and so on. Thus, the problem can be | + | We can look at each term individually: <math>{n\choose 0}</math> is the number of ways that a committee of size 0 can be chosen, <math>{n\choose 1}</math> is the number of ways that a committee of size 1 can be chosen, and so on. Thus, the problem can be restated as finding the number of committees of any size that can be formed from a group of <math>n</math> 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 <math>2^n</math> committees. |
== Further Problems == | == Further Problems == | ||
Latest revision as of 18:49, 16 July 2018
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
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 restated 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
.
