Combinatorial Proofs
Proving a counting identity by counting one set two different ways, instead of manipulating factorials algebraically.
Discrete Mathematics: An Open Introduction, Combinatorial Proofs
3 exercises
Exercise 1
Give a combinatorial proof of the identity .
Exercise 5
A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?
What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
What if she first selects her maid of honor, and then 5 other bridesmaids?
Explain why .
Exercise 7
Give a combinatorial proof of the identity .
Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.