The art of counting: permutations and combinations

Doing it the right way#

Formulas are usually easier to remember once they are understood from first principles. When recalling the difference between the formulas for permutations and combinations, the act of remembering can essentially be a split-second process of rediscovery—as long as a few concepts are understood properly.

In this blog, we cover the concepts of permutations and combinations, and show how the formulas to count permutations and combinations arise from a basic counting principle. We include some basic examples and some harder curve balls to help reinforce fundamental concepts.

Permutation vs. combination#

A combination is a collection of items that have no prescribed order. So a bag of things, a group of people, and a school of fish are all examples of a combination.

A permutation is a sequence of items with some specific order imposed on those items. If there’s a group of people standing in a queue, there’s a first person, a second person, and so on. That arrangement of individuals is an example of a permutation.

As evident from these definitions, the difference between a combination and a permutation is that a combination refers to an unordered set, whereas a permutation refers to an ordered linear arrangement of the elements of a set.

The concepts of combinations and permutations often arise in counting scenarios where we are interested in counting the number of permutations or combinations of a particular size. There are two convenient expressions that emphasize the size of a combination or a permutation: A combination consisting of $k$ elements (chosen from a possibly bigger set) is concisely referred to as a $k$-combination. Similarly, a permutation consisting of $k$ elements (chosen from a possibly bigger set) is called a $k$-permutation.

Commonly encountered counting problems#

A typical question we need to ask ourselves when solving a problem might look like one of the following:

• Counting $k$-permutations: We’ve got $n$ elements. How many ways are there to arrange $k$ of these in a linear order?

• Counting $k$-combinations: We’ve got $n$ elements. How many different ways are there to choose any $k$ of these?

Answering these is as easy as plugging the numbers into two formulas, but it’s far more useful in the long run to absorb the thought process that goes into arriving at those formulas. That’s because the thought process is immediately helpful for arriving at solutions to a wider range of problems. We start with a fundamental principle of counting.

A basic counting principle#

To complete a task consisting of two jobs, if there are $m$ ways to do the first job and $n$ ways to do the second, there are $m\times n$ ways to finish the task.

We use the following visual cue to help recall this counting principle:

We think about this as: if there are $m$ choices for the first decision, and $n$ choices for the second, then there are $m\times n$ ways to get the whole task done.

Example 1: If there are 2 different kinds of bread and 3 different kinds of spreads, how many ways are there to make a sandwich?

Since for each type of bread, we can use any of the 3 spreads, there are 6 different ways to make a sandwich.

Example 2: Suppose we want to decorate a card using glitter and a sticker. There are 3 kinds of paper, 2 kinds of glitter, and 5 different stickers to choose from. In how many ways can we make the card?

Since we can try all variations of a paper against the different types of glitter, and then for each of those $3 \times 2 = 6$ paper-and-glitter pairings, we can use any of the 5 stickers, therefore, there are $6 \times 5 = 30$ ways altogether.

Counting permutations and combinations are direct applications of this basic counting principle.

Counting permutations#

If there are $n$ objects, and we have to line them up, then there are $n$ choices for the item in the first place, $n-1$ choices for the item in the second place, and so on.

So there are $n\times (n-1)\times \cdots \times 1 = n!$ permutations.

Example: Let’s think about the number of ways to permute the animals shown below.

There are $4!$ permutations since that’s the number of ways to arrange the four animals.

Now let’s apply the same counting principle to count $k$-permutations on a set of $n$ elements.

Counting permutations of a subset#

If $k$ objects from a set of $n$ objects are to be arranged in a linear order, there are $n$ objects that can go in the first place. Once an object goes in the first place, there are $n-1$ choices for the second place, $n-2$ for the third place, and $n-(k-1)$ choices for the $k^{th}$ place.

So the total number of ways is

$$n \times (n-1) \times (n-2) \times \cdots \times (n- (k-1))$$

This is the number of $k$-permutations from a set of size $n$, but its not too easy on the eyes! Fortunately, we can make it more presentable, since the value of the expression remains unchanged when it’s multiplied and divided by the same quantity:

$$\begin{align*} n \times \cdots \times (n-k+1) &= \frac{n \times \cdots \times (n-k+1)}{(n-k)!}(n-k)!\\ &= \frac{n!}{(n-k)!} \end{align*}$$

And voilà, this neat and tidy formula is often expressed through the notation $P(n, k)$:

$$\begin{align*} P(n,k) &= \frac{n!}{(n-k)!} \end{align*}$$

Tip: In case of difficulty recalling this formula, we go back to square one by applying the basic counting principle and rediscovering it from scratch.

As each $k$-combination is a set of $k$ elements, it can be ordered in $k!$ different ways to get different $k$-permutations.

This can be expressed as:

$$\begin{align*} \underbrace{C(n,k)}_{\substack{\text{Number of}\\ \text{k-combinations}}} \times \underbrace{k!}_{\substack{\text{Number of ways to}\\ \text{ permute each} \\ \text{k-combination}} } &= \underbrace{P(n, k)}_{\substack{\text{Number of}\\ \text{k-permutations}}} \end{align*}$$

$$\begin{align*} \implies C(n,k)\times k! &= \frac{n!}{(n-k)!}\\ \implies \qquad C(n,k) &=\frac{n!}{k! (n-k)!} \end{align*}$$

An alternate notation for $C(n,k)$ is $\binom{n}{k}$, and this is our preferred choice of notation. Note that $\binom{n}{k}$ is commonly known as a binomial coefficient.

Takeaway: The formula for counting $k$-combinations from a set of $n$ elements is:

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

There might be other scenarios#

Having covered the basics, we should not be lulled into a false sense of security. In order to count effectively, we need to be aware of when not to apply these formulas.

One of the pitfalls to watch out for is a scenario where we are counting sequences of elements drawn from a set, such that each element can have a repeat occurrence within a sequence. Such sequences are called permutations with repetitions.

Example: Suppose we want to count bit strings of length 6 such that each character in the string is a 0 or a 1.

Since we are allowed to reuse the two characters (0 or 1), there are two choices for the first position, two choices for the second position, two choices for the third position, and so on. So the number of such bit strings is:

$$\underbrace{2 \times 2 \times \cdots \times 2}_{\text{For }6\ \text{positions}} = 2^6$$

Notice how we are able to arrive at the solution for the above problem by applying a simple counting argument. In general, if there are $n$ elements, the number of permutations of size $k$ with allowed repetitions is $n^k$.

$$\begin{align*} \underbrace{n \times n \times \cdots \times n}_{\ \text{For } k \text{ places}} = n^k \end{align*}$$

There might be other situations that require more fine-tuning. For now, we want to stop and consolidate what we’ve learned so far.

Practice makes perfect#

Let’s get more practice thinking about a mixed variety of counting problems!

How useful is all this?#

Knowing the difference between permutations and combinations is, without exaggeration, essential knowledge for most engineering disciplines. Here are some of the ways in which the concepts explored in this blog are applied in different kinds of content on the Educative platform:

• The Normal and Binomial Distribution lesson in a data science course employs these ideas to calculate probabilities.

• The running time for the code in the Solution: Permutations lesson of a course on coding interviews was calculated by realizing that there are $P(n,k)$ nodes in the recursion tree corresponding to the recursive code.

• The Subsets: Introduction lesson talks about a general pattern—seen in coding interviews—that pertains to finding combinations and permutations in different data structures.

• The size of the search space for a brute force algorithm referred to in the approximation algorithms blog was estimated using the ideas covered in this blog.

• The One-Time Pads lesson in a course on cryptography contains an example of counting permutations with allowed repetitions.

There is a lot more fun to be had with the kind of combinatorial reasoningThis refers to reasoning pertaining to combinatorics, which—broadly speaking—is the branch of mathematics that’s concerned with discrete structures with a special emphasis on counting. seen here. But that’s a topic for a different day. We hope this was interesting for you, and that you learned something new today!