Binomial Coefficient

{n\choose{k}}= \frac{n!}{k!(n-k)!}
n! = n(n-1)!

Complement: You can either choose a team of k members from a group of n people, or you choose all the n-k people from the group, that are NOT in the team. 

{n\choose{k}} = {n\choose{n-k}}

You can also combine the complement with the “production rule” (by that I mean, that in a multi-staged experiment where each stage has a number of alternatives, you can multiply the number of alternatives, e.g. 3 bus lines bring you to location A and from there you have 4 different possibilities to get to B, so there 3×4 possible ways to get from A to B.) Here is an example taken from “Introduction to Probability” from Blitzstein and Hwang:

You choose k people from a group of n. From these k people you choose one person, e.g. as captain. ${n\choose{k}} {k\choose{1}}$. But you could as well choose the captain first ${{n}\choose{1}}$ and from the remaining people (n-1) you choose the group of k-1: ${{n-1}\choose{k-1}}$, thus:

{n\choose{k}}{k\choose{1}} = {{n-1}\choose{k-1}} {{n}\choose{1}} 

So the above is just:

 {n\choose{k}}k = {{n-1}\choose{k-1}} n

A special case for this complement is Vandermonde’s Identity:

{{m+n}\choose{k}} = \sum_{j=0}^{k} {{m}\choose{j}}{{n}\choose{}k-j}

Additionally: n and k can be interpreted as coefficients of the the Pascal’s triangle. Then the coordinates in the next line in the triangle are by definition the sum of the adjacent “coordinates” of the current line, see the link for a more detailed explanation.

{n+1\choose{k+1}}={n\choose k}+{n\choose{k+1}}

Was this helpful?

2 / 0