0
$\begingroup$

So I've been having trouble making combinatorial proofs, as they're hard to start, I just can't simply think easily in the "committee"-way. So this is one of the many properties I have to prove.

$$\binom{n+k}{n+p}\binom{n+p}{p} = \binom{n+k}{n}\binom{k}{p}$$

I just don't know how to start. I'd appreciate if you'd help me and give some advice on how to do combinatorial proofs in general.

$\endgroup$
2
  • $\begingroup$ Thank you, I'll talk to my teacher about it. $\endgroup$
    – andrespm
    Commented Sep 24, 2017 at 4:01
  • 4
    $\begingroup$ You have a bunch of people. Choose some people to be on a committee, and within the committee, choose some of them to be on a subcommittee. Or, from the original bunch of people, choose some people to be committee-only (non-subcommittee), and from the leftovers, choose some to be committee-and-subcommittee. ... Advice: read this article. It specifically and openly talks about "committee selection" problems, how to solve them, how to write the answers, and also (!) how to know when that's a good approach. $\endgroup$ Commented Sep 24, 2017 at 4:37

1 Answer 1

0
$\begingroup$

In a combinatorial proof, we count the same set of objects in two different ways. Since the two expressions count the same thing, they must be equal.

Let's consider the left-hand side. The factor $\binom{n + k}{n + p}$ counts the number of ways we can select $n + p$ of the $n + k$ available people. The factor $\binom{n + p}{p}$ counts the number of ways we can select $p$ of those $n + p$ people. This suggests we are choosing a committee of $n + p$ people, from which a subcommittee of $p$ people is drawn.

For the right-hand side, we choose $n$ of the $n + k$ people to serve on the committee. From the remaining $k$ people, we select an additional $p$ people to serve on the committee, each of whom will also serve on the subcommittee.

$\endgroup$

You must log in to answer this question.

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