Counting

Foundations of mathematics

Introduction

In this article, we will learn to count! A strong foundation in counting is crucial to tackle advanced concepts such as probability.

Counting: Sum rule

Consider two tasks that cannot be done simultaneously. If one task can be done in \( n \) ways and the other in \( m \) ways, then the total number of ways to do either of these tasks is \( n + m \).

Example

Consider an election for the president of a country with two political parties, \( A \) and \( B \). The party \( A \) has \( 8 \) candidates and the party \( B \) has \( 9 \) candidates. The total number of possibilities for filling the post of the president is \( 8 + 9 = 17 \).

Counting: Product rule

Consider two sub-tasks that need to be performed sequentially to complete a task. If the first sub-task can be done in \( n \) ways and the second sub-task can be done in \( m \) ways, then the total number of ways of accomplishing the overall task is \( n m \).

Example

Consider lottery tickets that need to be labeled with an alphabet and a number between \( 0 \) to \( 100 \). There are \( 26 \) letters in the English alphabet. Thus, using the product rule, there are \( 26 \times 100 = 2600 \) possible lottery tickets.

Counting: Inclusion-exclusion principle

When two tasks can be done simultaneously, a naive application of the sum rule cannot be performed to count the number of ways of doing either of those tasks.

In this case, we first perform the sum rule (include) and then remove those possibilities that have been counted repeatedly (exclude). This is known as the inclusion-exclusion principle of counting.

Example

Consider the set \( A = \set{1,2} \) and the set \( B = \set{2,3} \). The union of the two sets is \( A \cup B = \set{1,2,3} \). Clearly, the cardinality of the union is not a simple addition of the cardinality of the two sets \( |A \cup B| \ne |A| + |B| \) because \( |A| = 2,~ |B| = 2,~ |A \cup B| = 3 \).

The element \( 2 \) has been counted twice. It is simultaneously present in both the sets, in their intersection \( A \cap B = \set{2} \). These need to be excluded from the count, by the inclusion-exclusion principle.

Hence, \( |A \cup B| = |A| + |B| - |A \cap B| \).

We show this visually using the Venn diagram below.

The pigeonhole principle

The pigenonhole principle states that if \( k + 1 \) objects are placed in \( k \) containers, then at least one container has two or more objects.

For example, in the following figure, notice the various ways in which 4 pigeons can occupy 3 holes, ignoring the ordering of the holes. In all the possible scenarios, there is at least one hole that is occupied by 2 or more pigeons. At least because, in Scenario 2, there are two holes that have 2 pigeons. From the other perspective, we also notice that there are at least two pigeons that share a hole.

Birthday example

In a room full of 367 people, there are at least two people with the same birthday as there are only 366 possible birthdays. In this example, people are the so-called pigeons and birthdays are the so-called holes. There is at least one birthday (hole) that is shared by two or more people (pigeons).

The generalized pigeonhole principle

If \( n \) objects are placed in \( k \) containers, then there is at least one container containing at least \( \left\lceil \frac{n}{k} \right\rceil \) objects.

For example, in the following figure, we show the various ways in which \( n = 5 \) pigeons can occupy \( k = 3 \) indistinguishable holes.

In this case,

\begin{equation} \left\lceil \frac{n}{k} \right\rceil = \left\lceil \frac{5}{3} \right\rceil = 2 \end{equation}

Notice that in all the scenarios, it is the case that there is at least one hole containing at least 2 pigeons.

Birthday example

Among a group of \( 40 \) people, there are at least \( \left\lceil \frac{40}{12} \right\rceil = 4 \) people born in the same month, because there are only \( 12 \) possible months.

Generalized pigeonhole principle calculator

Given \( n \) pigeons and \( r \) holes for placing them, figure out the result of applying the generalized pigeonhole principle.

Permutations

An ordered arrangement of a set of distinct objects is known as a permutation. For example, the following figure shows the possible permutations of a star, an oval, and a pentagon.

The number of possible arrangements of a set consisting of \( n \) distinct elements can be identified using the product rule as follows.

The first element can be chosen from the entire set in \( n \) possible ways. The next element in the arrangement can be chosen from the remaining \( n - 1\) elements in \( n - 1\) ways.

Following through this analysis till we exhaust the set, we get \( n (n-1) (n-2) \ldots 1 \) as the total number of possible arrangements. Note that this chain product is known as the factorial function \( n! = n (n-1) (n-2) \ldots 1 \).

Thus, the number of ways of arranging a set of \( n \) distinct elements is \( n! \).

There is no standard symbol for permutations of \( n \) objects. In mathematical literature, it is denoted as \( P(n,n) \) or \( \permutation{n}{n} \). In our articles, we will use the latter to distinguish it from the notation for probability.

Example

Suppose that you are planning a group portrait involving 3 people. The number of possible ways of arranging the people in the group for the pictures is \( 3! = 3 \times 2 \times 1 = 6 \) ways.

Permutation calculator

Calculate the possible permutations of \( n \) objects.

\(r\)-Permutation

An ordered arrangement of \( r \) elements of a set is known as an \(r\)-permutation. The number of \(r\)-permutations of a set of \( n \) elements is usually denoted as \( \permutation{n}{r} \). It can be calculated using the product rule as follows.

The first element can be chosen from the entire set in \( n \) possible ways. The next element in the arrangement can be chosen from the remaining \( n - 1\) elements in \( n - 1\) ways. Contining this calculation till we have filled the \( r \) spots in the arrangement results in \( n (n-1) (n-2) \ldots (n - r + 1) \) possible \(r\)-permutations.

We can simplify this further.

\begin{align} \permutation{n}{r} = & n (n-1) (n-2) \ldots (n-r+1) \\\\ = & \frac{ n (n-1) (n-2) \ldots (n-r+1) (n-r) (n-r-1) \ldots 1}{(n-r)(n-r-1) \ldots 1} \\\\ = & \frac{n!}{(n-r)!} \end{align}

Thus, \( \permutation{n}{r} = \frac{n!}{(n-r)!} \).

This can be intuitively understood with a tree diagram. In the following figure, we present the various permutations of the four letters \( \set{a, b, c, d} \). Each permutation is a path from the top to the bottom along the directed arrows.

For the first position, there are \( 4 \) options shown by the roots of the four sub-trees. So, \( \permutation{4}{1} = 4 \), the number of nodes at level 1. In general, it is always the case that \( \permutation{n}{1} = n \). This can be easily proved by substituting the formula above.

Each of the second positions has \( 3 \) options. Thus, the number of \(2\)-permutations are \( \permutation{4}{2} = 12 \), the total number of nodes at level 2.

For each of the third positions, there are \( 2 \) options. Thus, the number of \( 3 \)-permutations are \( \permutation{4}{3} = 24 \), the total number of nodes at level 3.

Finally, each of the fourth positions has only 1 options. Therefore, the number of \( 4 \)-permutations are \( \permutation{4}{4} = 24 \), the total number of nodes at level 4.

Note that \( \permutation{4}{4} = \permutation{4}{3} \). This is to be expected, because as we notice in the tree, there is only one remaining choice at the level 4 for each chain. This is in fact an important general result \( \permutation{n}{n} = \permutation{n}{n-1} \) and can be easily proved mathematically since \( 0! = 1! = 1 \).

Example

Consider arranging 3 vases on a dining table from a collection of 10 vases. There are \( \permutation{10}{3} = 10 \times 9 \times 8 = 720 \) different ways of arranging the vases.

\( r \)-Permutation calculator

Calculate the possible \( r \)-permutations of \( n \) objects

Combinations

An \(r\)-combination is an unordered selection of \( r \) elements from a set consisting of \( n \) distinct elements, such that \( 0 \le r \le n\). It is usually denoted as \( C(n,r) \), \( \combination{n}{r} \) or succinctly as \( {n \choose r} \), vocalized as "\( n \) choose \( r \)".

The number of possible \(r\)-combinations can be derived from the number of \(r\)-permutations.

In permutations, order of the elements matters, in combinations, it does not. All permutations involving the same \(r\) elements are the same combination. There will be \(\permutation{r}{r} = r! \) such permutations of the same \(r\)-elements. Thus, we need to divide the total number of \(r\)-permutations by the number of ways of re-arranging those \(r\) elements to arrive at combinations.

Thus,

\begin{align} \combination{n}{r} = & \frac{\permutation{n}{r}}{\permutation{r}{r}} \\\\ = & \frac{n!}{(n-r)! r!} \end{align}

Example

Consider selecting 3 representatives from a group of 100 people. There are \( C(100,3) = \frac{100!}{97! 3!} = \frac{100 \times 99 \times 98}{ 3 \times 2 \times 1} = 161700 \) possible ways of selecting the representatives.

Combinations calculator

Calculate the number of ways of choosing \( r \) elements from a set of \( n \) elements.

Pascal's identity

If \( n \) and \( r \) are positive integers such that \( n \ge r \), then

$$ C(n + 1, r) = C(n, r - 1) + C(n,r) $$

This relationship is known as Pascal's identity. This is because in the Pascal's triangle, an element is the sum of its two nearest neighbors in the row above.

Owing to this structure, we can visualize Pascal's identity as shown in the figure below.

It helps in arriving at the number of \(r\)-combination of a set consisting of \( n + 1 \) elements if the number of \(r\)-combinations of sets containing \(n\) elements is known.

Sum of all \(r\)-combinations

An interesting result in combinatorics shows that the sum of all \(r\)-combinations, for r = 1,2,\ldots,n on a set consisting of \( n \) elements is \( 2^n \). This means

$$ \sum_{r=0}^n C(n,r) = 2^n $$

This one is easy to prove. Consider a set \( \sA \) of \( n \) elements. How many possible subsets does \( \sA \) have? As many as there are bitstrings of length \( n \). Because a bitstring of length \( n \) can describe each subset of \( \sA \). A \( 1 \) in the \( k \)-th position in the bitstring indicates the presence of the \( k \)-th element of \( \sA \) in the subset and \( 0 \) indicates absence. Since each position has 2 options (0 and 1), and there are \( n \) positions, we have \( 2^n \) such bitstrings. Thus, there are \( 2^n \) possible subsets of \( \sA \).

Now, another way of computing the number of subsets is using the formula for \(C(n,r) \). There are \( C(n,r) \) possible subsets of \( \sA \) that contain exactly \( r\) elements, where \( 0 \le r \le n \). Thus, to count all possible subsets of \( \sA \), we just have to sum over values of \( r \).

Combining these two ways of calculating the number of subsets, we get the desired result.

$$ \sum_{r=0}^n C(n,r) = 2^n $$

Vandermonde's identity

For nonnegative integers \(n\), \(m\), and \(r\), such that \(r\) does not exceed \(n\) or \(m\), it is the case that

$$ C(m + n, r) = \sum_{k=0}^r C(m, r - k) C(n,k) $$

This relationship is known as Vandermonde's identity. It is useful in calculating the number of \(r\) combinations of a union of two disjoint sets, if it is easier to calculate the \(r\) combinations of the individuals sets.

Here's an intuitive proof of Vandermonde's identity. Imagine an election for the student council. There are \(m\) male candidates and \( n \) female candidates. There are \( r \) spots on the council. How many ways can these spots be filled?

Well, if you have been following along, we need to choose \( r \) from \( m + n \) total candidates it is \( C(m+n,r) \). The other way to look at it is how many females will be selected and consequently how many spots will be filled by males? If \( k \) female candidates get elected, then \( r - k \) males will appear on the committee. So, the number of ways that will happen is \( C(m,r-k) C(n,k) \). Varying the value of \( k \) from zero to \( r \), we can compute all possibilities. Comparing that number to the previously arrived at answer \( C(m+n,r) \), we get Vandermonde's identity.

$$ C(m + n, r) = \sum_{k=0}^r C(m, r - k) C(n,k) $$

The binomial theorem

Let \( x \) and \( y \) be variables. The sum of these two variables, \( x + y \), is known as a binomial expression.

If \( n \) is some positive integer, then

\begin{align} (x + y)^n = & \sum_{j=0}^n C(n,j) x^{n-j} y^j \\\\ = & C(n,0) x^n + C(n,1) x^{n-1}y + \ldots + C(n,n-1)x y^{n-1} + C(n,n) y^n \end{align}

This result is known as the binomial theorem. It is useful in listing out the terms of powers of such binomial expressions.

Example

Suppose we wish to find the coefficient of \( x^3y^6 \) in the expansion of \( (x+y)^9 \). Using the binomial theorem it is easy to note that it will be \( C(9,6) \).

Permutations with repetition

If the same element can be repeated in a permutation, then the number of \(r\)-permutations of a set of \( n \) elements is \( n^r \).

This result is a straightforward application of the product rule of counting. In each permutation, the first spot can be filled in \( n \) ways. Since repetition is allowed, the second spot can also be filled in \( n \) ways. Thus, each of the \( r \) spots can be filled in \( n \) ways. By product rule, the number of \(r\)-permutations with repetitions is then \( n^r \).

Permutations with repetition calculator

Calculate the possible \( r \)-permutations of \( n \) objects, if the same element can be repeated multiple times.

Combinations with repetition

If the same element can be repeated in a combination, then the number of \(r\)-combinations of a set of \( n \) elements is \( C(n + r - 1, r) \)

Arriving at this result requires some creative thinking. When repetition is allowed, then a resulting combination will consist of some repeated elements and some missing elements. Suppose the \( n \) distinct elements are separated by \( n-1 \) \(x\)'s. Also, imagine that for each repetition of an element, a \( 0 \) is placed at its location.

For example, a \(6\)-combination from a set of 4 elements may look like \( 0~0~x~x~0~0~0~x~0 \), as shown in the figure below.

This symbolic notation shows that in the \(6\)-combination,

  1. the first element is repeated two times
  2. the second element is missing
  3. the third element is repeated three times
  4. and, the fourth element occurs only once.

For this symbolic notation, there are a total of \( n - 1 + r \) positions in which to place \( r \) \( 0\)'s. The remaining positions will be the \( n - 1 \) \(x\)'s. The total number of ways of doing so is then \( C(n + r - 1, r) \).

Example

Suppose we wish to pack a fruit basked with oranges, apples, and mangoes such that the total number of fruits in the basket is 10. Since in our case we have a choice of 3 fruits, so n = 3. The number of ways of filling up such a basket is then \( C(3 + 10 - 1, 10) = C(12, 10) \)

Combinations with repetition calculator

Calculate the number of ways of choosing \( r \) elements from a set of \( n \) elements, when repetitions are allowed.

Permutations with indistinguishable objects

Consider the word "BOOKKEEPER". How many words can be generated by reordering the letters of this word? There are 10 letters, but some letters are repeated. To avoid overcounting, the frequency of each letter must be taken into account to arrive at the result.

Consider a more general problem involving a collection of \( n \) elements including repetitions. In the collection there are \( n_1 \) repetitions of the element of type 1, \( n_2 \) of type 2, \( \ldots \), and \( n_k \) repetitions for the type \( k \).

Imagine that all \( n \) elements were distinct then, we know that the number of possible rearrangements is \( P(n,n) = n! \). Of these, \( n_1! \) permutations consist of rearrangement of the \( n_1 \) repetitions of the elements of type 1. Similarly, there are \( n_2!, n_3!, \ldots n_k! \) permutations of rearrangements of the \(n_2, n_3, \ldots, n_k \) indistinguishable elements of types \(2, 3, \ldots, k \).

Thus, the number of different permutations of \( n \) elements containing groups of indistinguishable objects is

$$ \frac{n!}{n_1! n_2! \ldots n_k!} $$

Distributing objects into distinguishable boxes

Consider the task of placing \(n\) distinguishable objects in \(k\) distinguishable boxes. How many ways to achieve this?

Imagine all the objects lined up from left-to-right. The first \(n_1\) objects are assigned to first box, the next \(n_2\) to the second, and so on.

There are \(n!\) permutations for lining up the objects. Within the \(i\)-th box, there are \(n_i\) objects. These can be arranged within that box in \(n_i!\) ways. We do not care about these within-box rearrangements, so that becomes a divisor for the overall number of permutations.

Thus, the number of ways to distribute \( n \) distinguishable objects into \( k \) distinguishable boxes, so that \( n_i \) objects are placed into the box \( i \), for \( i = 1, 2, \ldots, k \) equals

$$ \frac{n!}{n_1! n_2! \ldots n_k!} $$

Example

Consider a 4-player card game that involves distributing 8 cards to each player from a standard 52 card deck. To count the number of ways this can be accomplished, know that there are 5 total "boxes" that we need to distribute the cards into. One for each player to hold their 8 cards and one for the remaining \( 52 - 4 \times 8 = 20 \) cards.

Thus, the number of ways is then

$$ \frac{52!}{8! 8! 8! 8! 20!} $$

Next-article

With a sound understanding of counting, you are ready to tackle probability. You may also further your understanding by taking on advanced counting.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Subscribe for article updates

Stay up to date with new material for free.