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.

  • $\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


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.


You must log in to answer this question.

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