Difference between revisions of "Committee forming"

Revision as of 06:58, 14 October 2009

Committee forming is one technique for solving certain combinatorics problems.

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 $12\cdot 11\cdot 10 = 1320$ total committees.

However, the order we choose them does not matter. So we have overcounted. Since there are $3! = 6$ ways in which each distinct committee could have been chosen, we divide our result by 6 to get $\frac{1320}6 = 220$ .

Note: there is a special notation for expressing the number of ways to choose a committee of size $k$ from a set of size $n$ . We use ${n\choose k}$ 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.$

Solution

We can look at each term individually: ${n\choose 0}$ is the number of ways that a committee of size 0 can be chosen, ${n\choose 1}$ 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 $n$ 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 $2^n$ 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 ${3\choose 0} + {3\choose 1} + {3\choose 2} + {3\choose 3}$ .

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 ${n\choose k} = {n\choose n-k}$ .
Prove Pascal's identity: ${n\choose k} = {n-1\choose k} + {n-1\choose k-1}$
Prove that ${m+n\choose k} = {m\choose 0}{n\choose k} + {m\choose 1}{n\choose k-1} + \cdots + {m\choose k}{n\choose 0}.$

@@ Line 32: / Line 32: @@
 # 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 <math>{n\choose k} = {n\choose n-k}</math>.
-# Prove [[Pascal]]'s identity: <center><math>{n\choose k} = {n-1\choose k} + {n-1\choose k-1}</math></center>
+# Prove [[Blaise Pascal | Pascal]]'s identity: <center><math>{n\choose k} = {n-1\choose k} + {n-1\choose k-1}</math></center>
 # Prove that <center><math> {m+n\choose k} = {m\choose 0}{n\choose k} + {m\choose 1}{n\choose k-1} + \cdots + {m\choose k}{n\choose 0}.</math></center>

Page

Toolbox

Search

Difference between revisions of "Committee forming"

Revision as of 06:58, 14 October 2009

Contents

Introduction

Problem

Solution

Proving Combinatorial Identities

Problem

Solution

Further Problems

Introductory Problems

Intermediate Problems

See also