AI Tutor
Library
›Library›Mathematics›Discrete Mathematics: An Open Introduction›Counting›Combinatorial Proofs
Back to Discrete Mathematics: An Open Introduction

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

Status
FlagsLoading your progress…

3 exercises

Exercise 1

Give a combinatorial proof of the identity 2+2+2=3⋅22+2+2 = 3\cdot 2.

2.5

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?

  1. What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?

  2. What if she first selects her maid of honor, and then 5 other bridesmaids?

  3. Explain why 6(156)=15(145)6 {15 \choose 6} = 15 {14 \choose 5}.

2.5

Exercise 7

Give a combinatorial proof of the identity (n2)(n−2k−2)=(nk)(k2){n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}.

2.5
Additive and Multiplicative PrinciplesStars and Bars

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.

AI Tutor

A study tool built on open educational resources. Content from OpenStax and other openly licensed textbooks — every book, section and exercise page carries its source’s license and attribution.

Product
  • About AI Tutor
  • Library
  • Premium
Legal
  • Terms of Service
  • Privacy Policy
© 2026 AI Tutor. Openly licensed content is attributed to its authors under their respective licenses.