Using Combinatorial Reasoning
1. I am having a super awesome math party and want to invite 17 out of my n friends (n is very large).
a) How many ways can I do this with no restrictions?
b) How many ways can I do this where Lance is definitely one of the invitees?
c) How many ways if I will definitely not invite Lance? (He’s out of town, filming the new season of The Bachelor.)
d) Combine (a), (b) and (c) to create a new expression for.
e) Prove the following identity by completing each of the answers to the given question.
Question: How many ways are there to throw a party where you invite exactly 17 of your n friends? Suppose you have identified one of your friends, call him Lance.
Answer #1: There are possible parties because
Answer #2: On the other hand, there are possible parties because
f) Explain why showing that both of these are answers to the given question suffices to establish the identity.
2. I would like to count the number of different committees (of any size) that could be formed from a group of n people.
a) Using the multiplication rule, but not combinations, count the number of ways you could form a committee (or any size) from a group of n people.
b) Using combinations and addition rule, count the number of ways you could form a committee (of any size) from a group of n people.
c) Prove the following identity by completing each of the answers to the given question.
Question: How many ways are there to make a committee (of any size) from a group of n people?
Answer #1: There are possible committees because
Answer #2: On the other hand, there are possible committees because
The approach we used to prove each of these identities is known as Combinatorial Reasoning or Combinatorial Proof.
We establish an identity by posing a counting question and giving two different answers. Since the two answers count the same thing in distinct ways, we conclude they must be equal.
Use combinatorial reasoning to demonstrate the following identities. Each solution will consist of a question and two answers, one for each side of the identity.
3.
Question: How many ways are there to throw a party where you invite exactly k or your n friends?
Answer #1: There are possible parties because
Answer #2: Say that “Lance” is one of my n friends. There are possible parties because
4.
Question: How many ways can you choose a committee of k people from a group of n and also pick a president?
Answer #1:
Answer #2:
5.
Question: How many ways are there to select a committee (of any size) from a group of n people and also select a president? (Note that this excludes the empty committee).
Answer #1:
Answer #2:
Question:
Answer #1:
Answer #2: On the other hand, there are groups of size n. We can see this by dividing the 2n people up into two equally sized groups and
7. Given ,
(Hint: Think of m as “men” and w as “women”)
Question:
Answer #1:
Answer #2:
8.
Question:
Answer #1:
Answer #2: