Since the concept of “n choose k” seems to appear a lot in my life I decided I would make a quick post explaining the intuition behind it. Let’s start with a simple example.

Say we had a set of three greek characters representing the names of three friends, \( F = \{ \alpha, \beta, \gamma \}\) and we are interested in knowing how many uniquely paired matches could be played between two competitors of the friends in table tennis. If we began choosing a competitor at random, there would be 3 friends to pick from. The next competitor, there would be only 2 friends to pick from. We can easily see that there are \(3 \times 2 = 6\) ways of choosing competitors \(P = \{ (\alpha, \beta) , (\alpha, \gamma), (\beta, \gamma), (\beta, \alpha), (\gamma, \alpha) , (\gamma, \beta) \}\) . The \(3 \times 2 \) can similarly be writted as \(\frac{3!}{(3-2)!}. \) As you can see order matters in this pairing and this is called a Permutation. We only had \(n = 3\) friends to participate in our unique matches of \(k = 2\) competitors. In general, we would say the permutations of games denoted by \(n\) friends and \(k\) competitors is:

However this does not account for when we have no care for order, because let’s face it, if your friend is playing on a specific side, the game should be equal and we won’t care the “order” that our equation just accounted for. Consider the possibilities we had from our previous example \(P = \{ (\alpha, \beta) , (\alpha, \gamma), (\beta, \gamma), (\beta, \alpha), (\gamma, \alpha) , (\gamma, \beta) \}\) . There seems to be some redundancy and we can remove a few, resulting in \(C = \{ (\alpha, \beta) , (\alpha, \gamma), (\beta, \gamma) \}\) . This is called a combination. Notice the combination is of size 3 while the permutation is of size 6. You simply divide by \(k\) competitors you are considering in this game. Then we can see that a combination is defined by:

And there you have it. Permutation deals with ordered arrangements and combinations deals with unordered combinations.