2
$\begingroup$

This is a bonus question on a take home quiz. My teacher has not introduced us to combinatorial proofs, just the basics of combinatorics. Does anyone know the correct format for such a proof? Help with the problem would be appreciated as well!

$\endgroup$
2
  • $\begingroup$ The idea is to find something that both sides of the equality can be seen to count. If you search the site for combinatorial proof, you’ll find many examples. $\endgroup$ Mar 18, 2016 at 15:51
  • 1
    $\begingroup$ Worded it improperly, sorry! This is a practice quiz. If we're able to demonstrate a thought process behind combinatorial proofs, we're given extra credit. $\endgroup$ Mar 18, 2016 at 15:52

1 Answer 1

5
$\begingroup$

Imagine you are to form a chaired committee of $k+1$ members from a pool of $n$ people. You can either pick the chair first and then the other $k$ members of the committee, or the committee first and then choose one of the $k+1$ members as the chair.

$\endgroup$
2
  • $\begingroup$ I wasn't sure what "find a combinatorial proof" meant. Would it be an example like this? If so, it makes perfect sense to me with just about any example from everyday life. I originally thought it meant to prove that equation. $\endgroup$ Mar 18, 2016 at 15:58
  • 2
    $\begingroup$ @d3m0nxdrums To create a combinatorial proof, you define a set and then count it in two different ways to show they are equal. This is an example of this, with the set defined using words rather than symbols. $\endgroup$
    – J. Bush
    Mar 18, 2016 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .