Introduction to Combinatorics

Last modified:

The following is a short and simple introduction to some of the most elementary concepts in enumerative combinatorics. It assumes almost no mathematical background beyond basic algebra. It provides good background material for solving problems in discrete probability.

Books on Combinatorics

This is a list of books that cover combinatorics in greater depth.

Combinatorics Problems and Solutions
This book contains over 200 combinatorics problems with detailed solutions. The problems start easy and get progressively more difficult. There is no better way to learn the subject than by solving problems.
Proofs That Really Count
This wonderful little book shows how to prove combinatorial identities. The presentation is simple and engaging with very little background required.
A Walk Through Combinatorics
This book is at only a slightly higher level than what's presented here. It's a good followup to this introduction.
Enumerative Combinatorics
This book by Richard Stanley will take you as deep as you want to go into the subject. After reading it you will be a real combinatorialist and will be ready to contribute to the field.

Set Enumeration

Much of combinatorics involves counting the number of elements in a set and the absolute simplest way to do that is by enumeration. This is the form of counting that every child first learns. You take the elements of the set one by one and assign integers to them starting with 1. The largest integer used is the number of elements in the set. This is called the size of the set or its cardinality. For example the set of odd decimal digits is {1, 3, 5, 7, 9}. The size of this set is 5.

Let’s say you want to snack on some fruit. You look in the fridge and find the following set of fruits: {apple, orange, banana, mango}. There are 4 fruits in this set so there are 4 ways you can have a snack. You probably get the idea behind simple enumeration.

If there were nothing more to combinatorics then it would be time to move on to something else. Unfortunately it's not always so simple. The elements of a set are often just defined in terms of some rule or some method of construction and there could be millions, billions or an infinite number of them. Take for example the set of all possible ways that 5 cards can be shuffled. There are 120 ways to shuffle them and you could in principle list all the ways and then count them but this is tedious to say the least. In general it's not practical to just list the elements of a set and then count them. It takes more ingenuity than that.

Sum Rule

The next step up in counting is called the sum rule. Here instead of just one set, we have two or more. In how many ways can an element be selected from one of the sets? For example if we have the set of 26 letters in the English language and the set of 10 decimal digits, how many ways can a letter or a digit be selected? There are 26 choices for the letter and another 10 choices for the digit so the total number of choices is 26+10=36.

Going back to the snacks. Let’s say that in addition to fruit you are considering a salty snack. In the cupboard you find the following set of snacks: {potato chips, tortilla chips, pretzels}. These are 3 more choices you have in addition to the 4 fruits so the total number of choices is 4+3=7. The assumption here is that you will have a fruit or a salty snack but not both. We will get to the number of ways of having both in the next section.

To sum it up, the sum rule says that if you have two or more sets then the number of ways of selecting an element from one or the other of the sets is the sum of the sizes of the sets. For \(k\) sets with sizes \(n_1\) through \(n_k\) the number of ways of selecting an element from any one of the sets is

\[N = n_1 + n_2 + \cdots + n_k\]

There is one thing you have to be careful about. There can be no overlap between the sets. In other words the same element cannot appear in more than one set. Another way of saying this is that the intersection of the sets must be the empty or null set. If there is a nonempty intersection then you have to take this into account. How to do that is covered in the section on the inclusion-exclusion principle below. There may however be situations where the same element appears in more than one set for a reason and each appearance has to be counted. It depends on the problem so be careful.

Product Rule

Now suppose we have 2 or more sets and the question is how many ways can one element be selected from each of the sets. Let’s return to the snacks. Now we’re really hungry so we decide to have both a fruit and a salty snack. What are the possibilities? If we go for an apple then we can still pick any of the 3 salty snacks so there are 3 possibilities in this case. The same is true for the orange, banana, and mango. Each can be paired up with one of the 3 salty snacks. For each of the 4 fruits there are 3 possible salty snacks so the total number of ways of choosing a fruit and a salty snack is 4*3=12. They are all listed below.

\[\begin{array}{lll} \mbox{(apple, potato chips)} & \mbox{(apple, tortilla chips)} & \mbox{(apple, pretzels)} \\ \mbox{(orange, potato chips)} & \mbox{(orange, tortilla chips)} & \mbox{(orange, pretzels)} \\ \mbox{(banana, potato chips)} & \mbox{(banana, tortilla chips)} & \mbox{(banana, pretzels)} \\ \mbox{(mango, potato chips)} & \mbox{(mango, tortilla chips)} & \mbox{(mango, pretzels)} \end{array}\]

So for 2 sets you multiply their sizes to get the number of ways of making a selection of one element from each set. But what if we’re thirsty and need to make a choice from a set of drinks {water, soda, juice, coffee, tea, beer}. This is a third set of 6 elements to choose from. For every one of the above combinations of snacks we can choose one of these 6 drinks, so the total number of possible snacks and drinks is 4*3*6=72. That’s quite a variety to choose from.

The general pattern should be clear. If you have \(k\) sets with sizes \(n_1\) through \(n_k\) then the number of ways of selecting one element from each of the sets is:

\[N = n_1 * n_2 * \cdots * n_k\]

We will call this the product rule.

The sum and product rules are sometimes used together. Let's say you have three sets A, B, and C with sizes \(n_A\), \(n_B\), and \(n_C\). How many ways can you select two elements from two different sets? The product rule says that the number of ways of selecting one element from A and one from B is \(n_A*n_B\). This is one set of possibilities. You can also select one element from A and one from C in \(n_A*n_C\) ways. This is another set of possibilities. Finally you can make one selection from B and one from C in \(n_B*n_C\) ways. You have three sets of ways to make the selection and you have to pick from one of them so the sum rule says the total number of ways to make the selection is

\[N = n_A*n_B + n_A*n_C + n_B*n_C\]

Permutations

Instead of selecting just one element from a set suppose we want to select \(k\) elements. How many ways can this be done? If the set has size \(n\) then there are \(n\) choices for the first element. The second choice is made from the remaining \(n-1\) elements, so there are \(n-1\) choices. The third element can be chosen in \(n-2\) ways and so on for the remaining elements. The number of ways of choosing, according to the product rule, must then be

\[\tag{10}N=n*(n-1)*(n-2)*\cdots*(n-k+1)\]

This product of a sequence of consecutive numbers occurs so often that a special notation is used to represent it. If you multiply all the integers between 1 and \(n\) it is called the factorial of \(n\) and the notation is:

\[\tag{20}n!=n*(n-1)*(n-2)*\cdots*3*2*1\]

with \(0!\) being defined as equal to 1. As an example the factorial of 5 is \(5!=5*4*3*2*1=120\). With this notation equation 10 can be written as:

\[N=\frac{n!}{(n-k)!}\]

The number of ways of selecting all \(n\) objects in the set is just \(n!\). It may seem like there is only one way to select all the elements in the set but that is only true if the order in which the elements are selected is not important. We have been assuming that order of selection is important so that selecting dog and then cat from the set of animals is different than selecting cat and then dog. The number of ways of selecting all the elements in this sense is equal to the number of ways that the elements can be ordered. Each way of ordering the elements is called a permutation. There are \(n!\) permutations of \(n\) elements, and \(n!/(n-k)!\) permutations of \(n\) elements taken \(k\) at a time. We will give this expression a name, \(P(n,k)\), where \(P\) stands for permutation, so that

\[\tag{30}P(n,k)=\frac{n!}{(n-k)!}\]

We should actually refer to the permutations discussed above as linear permutations since they are formed by arranging the elements in some linear order. There is another kind of permutation called a circular permutation where the elements are arranged in a circular order. For a circular permutation there is no natural beginning or end of the arrangement and any circular shift of the elements around the circle does not count as a new arrangement. This should mean that there are fewer circular permutations of \(n\) elements than there are linear permutations. Indeed there are only (\(n-1)!\) circular permutations as opposed to \(n!\) linear permutations. To see this, pick a point on the circle to correspond with the start of a linear permutation. If you put one of the linear permutations on the circle then every one of its \(n\) possible circular shifts will correspond to a different linear permutation when read from the starting point but each of these shifts is counted as the same circular permutation. For every circular permutation there are \(n\) linear permutations therefor the number of circular permutations must be \(n!/n=(n-1)!\).

The same argument applies to the number of circular permutations of \(n\) elements taken \(k\) at a time. There are \(k\) circular shifts of the \(k\) elements that correspond to different linear permutations but the same circular permutation. So to get the number of circular permutations, divide the linear permutations by \(k\)

\[N=\frac{n!}{k(n-k)!}\]

Combinations

In some cases the order in which \(k\) elements are selected from \(n\) is not important. Equation 30 counts all the ways that \(k\) elements can be selected, including selecting the same elements but in a different order. For example if we are interested in how many 3 letter words can be formed from the English alphabet then the order is important and equation 30 says there are

\[P(26,3)=\frac{26!}{23!}=26*25*24=15,600\]

possible words. This includes for example the six words: abc, bca, cab, bac, cba, acb. All these words have the same letters. For every set of 3 letters all 6 ways they can be arranged is counted in the equation. If only the letters are important and not their order then we have to divide by 6 to get 15,600/6=2,600 unique ways of choosing 3 letters.

In general there are \(k!\) ways that \(k\) elements can be ordered so if the order is not important then the number of ways that \(k\) elements can be chosen from \(n\) is

\[\frac{n!}{k!(n-k)!}\]

This is equal to the number of \(k\) element subsets that can be formed from a set of \(n\) elements (the order of elements in a set or subset is irrelevant). It is called the number of combinations of \(n\) elements taken \(k\) at a time and it is given a special notation:

\[\tag{40}\binom{n}{k}=\frac{n!}{k!(n-k)!}\]

For convenience the equation is also referred to with the function name \(C(n,k)\), and stated verbally as “\(n\) choose \(k\)”.

The term \(\binom{n}{k}\) is called a binomial coefficient since it appears in the expansion of binomials. If you multiply out the binomial \((x+1)^n\) then the coefficient of \(x^k\) in the expansion will be \(\binom{n}{k}\). For example \((x+1)^5\) is equal to

\[(x+1)^5=x^5+5x^4+10x^3+10x^2+5x+1\]

The coefficient of \(x^3\) in this equation is \(\binom{5}{3}=10\). Note that this is also equal to the coefficient of \(x^2\) so we have \(\binom{5}{3}=\binom{5}{2}\). In general binomial coefficients obey:

\[\binom{n}{k}=\binom{n}{n-k}\]

which should be obvious from the way they are defined in equation 40.

Binomial coefficients have many useful and interesting properties. For example summing them for all possible values of k gives

\[\tag{50}\sum_{k=0}^n \binom{n}{k} = 2^n\]

You can see this from the fact that the coefficients appear in the expansion of \((x+1)^n\). Write out the expansion, set \(x=1\) and you get equation 50. Another useful relationship is

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]

This can easily be proven algebraically.

Multinomial Coefficients

The binomial coefficient \(\binom{n}{k}\) counts the number of ways you can choose \(k\) elements from \(n\) when the order of choice does not matter. You can also look at it as the number of ways that a set of \(n\) elements can be divided into 2 subsets with \(k\) elements in one subset and \(n-k\) elements in the other. This of course leads to the question of how many ways you can divide the elements into 3 or more subsets. Suppose we want to divide the \(n\) elements into 3 subsets with \(k\) elements in the first subset, \(l\) in the second, and \(n-k-l\) in the third. The way to do this is straightforward. First select the \(k\) elements for the first subset which divides the \(n\) elements into a \(k\) element subset and a \(n-k\) element subset. The number of ways of doing this is \(\binom{n}{k}\). Next select the \(l\) elements for the second subset from the \(n-k\) element subset. This can be done in \(\binom{n-k}{l}\) ways. Now we have 3 subsets of the original \(n\) elements of size \(k\), \(l\), and \(n-k-l\) and the number of ways of forming these subsets is (using the product rule):

\[\binom{n}{k}\binom{n-k}{l}=\frac{n!}{k!(n-k)!}\frac{(n-k)!}{l!(n-k-l)!}=\frac{n!}{k!l!(n-k-l)!}\]

The extension to more than 3 subsets should be obvious. Let's say we want \(r\) subsets with \(k_i\) elements in subset \(i=1,2,\ldots,r\). This should completely divide up the \(n\) elements so that \(k_1+k_2+\cdots+k_r=n\). The number of ways the subsets can be formed is

\[\binom{n}{k_1}\binom{n-k_1}{k_2}\cdots\binom{n-k_1-k_2-\cdots-k_{r-1}}{k_r}\]

When this equation is written out and simplified it becomes

\[\tag{60}\frac{n!}{k_1! k_2! \cdots k_r!} = \binom{n}{k_1,k_2,\cdots,k_r}\]

where we have assigned a new notation on the right side of the equation. This new notation is called a multinomial coefficient. The coefficients appear when you expand a multinomial. In this case they would appear in the expansion of \((x_1+x_2+\cdots+x_r)^n\). The coefficient of \(x_1^{k_1}x_2^{k_2}\cdots x_r^{k_r}\) in the expansion is given by equation 60.

Multinomial coefficients come up in a variety of contexts. Suppose for example you have a collection of \(n\) letters with \(k_1\) of them being a’s, \(k_2\) of them being b’s, \(k_3\) of them being c’s and the remaining \(n-k_1-k_2-k_3\) all different. How many unique \(n\) letter words can you construct? The answer is given by a multinomial coefficient. In this case the \(n\) string positions are the objects to choose from. Choose \(k_1\) positions for the a’s, \(k_2\) positions for the b’s, \(k_3\) positions for the c’s and one position for each of the remaining \(n-k_1-k_2-k_3\) different letters. The number of ways of doing this is

\[\binom{n}{k_1,k_2,k_3,1,1,\cdots,1}=\frac{n!}{k_1! k_2! k_3!}\]

where the \(n-k_1-k_2-k_3\) factors equal to \(1!=1\) have not been explicitly included on the right side of the equation. What we have done is divide the set of \(n\) string positions into \(n-k_1-k_2-k_3+3\) subsets with \(k_1\) elements in one subset, \(k_2\) in another, \(k_3\) in another, and 1 element in each of \(n-k_1-k_2-k_3\) subsets.

Balls in Boxes

A large number of counting problems can be stated in terms of placing balls into boxes (or cells, urns, whatever you like). Suppose for example we have 12 people and 12 fruits: 2 mangos, 4 apples, and 6 oranges. In how many ways can each person get one of the fruits? In this case the people are balls and they can be placed into one of 3 boxes, a mango box, an apple box, and an orange box. 2 people can be put in the mango box, 4 can go in the apple box and 6 can go in the orange box. When stated this way you can see that the people are being divided into 3 groups or sets and the number of ways you can do this is given by a multinomial coefficient (see previous section)

\[\binom{12}{2, 4, 6}=\frac{12!}{2! 4! 6!}=13,860\]

This is an example of placing distinguishable balls into boxes. In general if you have \(m\) balls to put into \(r\) boxes so that box \(i\) has \(m_i\) balls then the number of ways to do it is given by the multinomial coefficient

\[\tag{70}\binom{m}{m_1,m_2,\cdots,m_r}=\frac{m!}{m_1! m_2! \cdots m_r!}\]

Another problem of the same type is finding the number of permutations of a set of letters that may not all be unique. Take the word banana for example. There are 3 a’s, 2 n’s and one b so not all \(6!=720\) permutations of these letters will produce a unique word. You can for example switch the 2 n’s in banana and still get a banana. If the 3 a’s are uniquely identified in some way then they can be arranged in \(3!=6\) ways but if you then remove the identifiers the 6 arrangements become indistinguishable. So the number of unique permutations must be given by the multinomial coefficient:

\[\binom{6}{3, 2, 1}=\frac{6!}{3! 2! 1!}=60\]

This kind of permutation of a set of objects where you have groups of objects of the same type is called a multiset permutation. Finding the number of multiset permutations is the same as the fruit distribution problem discussed above and it can also be interpreted in terms of putting balls into boxes. In the banana example the balls are the 6 string positions and there are 3 boxes, a "b" box, a "n" box and an "a" box. The "b" box takes one ball, the "n" box takes 2, and the "a" box takes 3. In general the number of multiset permutations of \(m\) objects of \(r\) different types, where the number of objects of type \(i\) is \(m_i\), is given by the multinomial coefficient in equation 70.

In the two examples discussed above the balls were distinguishable. People are generally distinguishable and letter position in a word is clearly defined and therefor distinguishable. In some cases the balls are considered indistinguishable and the problem is to count the number of ways the \(m\) balls can be put into \(r\) boxes. In the fruit example suppose we have an unlimited supply of each type of fruit and we only want to know how many ways 12 people can take 3 kinds of fruit. Again the 3 fruits are represented by 3 boxes and the people are now represented by 12 indistinguishable balls. If \(|\) symbolizes the side of a box and \(*\) symbolizes a ball then one way of distributing 12 balls (people) into 3 boxes (fruits) is as follows: \(**|******|****\). In this case 2 people got mangos (first box), 6 people got apples (second box), and 4 people got oranges (third box). Now how many total ways can the 12 balls be put into the 3 boxes? Each distribution can be represented by 14 symbols, 2 \(|\) symbols representing the sides of the boxes and 12 \(*\) symbols representing the people. A distribution is fixed by selecting 2 of the 14 symbols to be \(|\) and then letting the rest of the symbols be \(*\). The number of ways of selecting 2 objects from 14 is

\[\binom{14}{2}=\frac{14!}{2! 12!}=\frac{14*13}{2}=91\]

This is the number of ways that 12 people can get 3 kinds of fruit. In general if the balls are indistinguishable then every solution of the equation \(m_1+m_2+\cdots+m_r=m\) where each \(m_i\) is an integer, is a way of placing \(m\) balls into \(r\) boxes. The numbers \(m_i\) are called occupancy numbers. When representing this using the stars and bars notation, as in the above example, there will be \(r-1\) vertical bars for the sides of the boxes and \(m\) stars for the balls giving a total of \(m+r-1\) symbols. The number of ways of selecting \(r-1\) of the symbols to be bars or \(m\) of the symbols to be stars is

\[\tag{80}\binom{m+r-1}{m}=\binom{m+r-1}{r-1}\]

This is the number of ways that \(m\) indistinguishable balls can be placed into \(r\) boxes.

Here is another example that gives a slightly different way of looking at this sort of problem. We have a lottery that involves selecting 4 numbers from the numbers 1 through 20 where any number can be selected multiple times. In other words let's say the first number selected is 7. The number is then put back into the hopper so that it could be selected again. This is called sampling with replacement. In most lotteries, the order in which the numbers are selected makes no difference. The only thing that matters is the final set of numbers selected. So this is another example of putting indistinguishable balls into boxes. The boxes in this case are the numbers 1 through 20 and the balls are the four selections. Using equation 80 with \(r=20\) and \(m=4\), the number of possible lottery tickets is

\[\binom{4+20-1}{4}=\binom{23}{4}=8,855\]

Another way of looking at this problem is as follows. Let the four numbers in a lottery drawing be \(r_1\), \(r_2\), \(r_3\), and \(r_4\) where they are labeled so that:

\[1 \le r_1 \le r_2 \le r_3 \le r_4 \le 20\]

Now define a new set of 4 numbers: \(s_1=r_1\), \(s_2=r_2+1\), \(s_3=r_3+2\), \(s_4=r_4+3\). These numbers will all be different and they obey the relation:

\[1 \le s_1 < s_2 < s_3 < s_4 \le 23\]

This shows that there is a one to one correspondence between the act of selecting 4 numbers from 1 to 20 with replacement and selecting 4 numbers from 1 to 23 without replacement. The number of ways of selecting 4 unique numbers from 1 to 23, when the order is not important, is given by the binomial coefficient \(\binom{23}{4}=8,855\), which is the same answer we found above. The general idea is that the number of ways to select \(m\) things from \(r\) with replacement (repetition allowed) and with order not important, is the same as the number of ways of selecting \(m\) things from \(m+r-1\) things with order not important. It is a somewhat different way of looking at equation 80. It is also an example of what is called a bijection in combinatorics. If you can show that there is a one to one mapping between the elements of 2 sets, so that every element of one set has one and only one corresponding element in the other set, then a counting problem in one set can be translated into a counting problem in the other.

Inclusion-Exclusion Principle

If you are told that in a group of people there are 8 males and 12 females then you know there must be 20 people in the group since every person is either male or female and never both. The male and female set is said to be a partition of the set of people. In general you can have situations where an object is simultaneously a member of more than one set. Then you can not find the total number of objects by summing the number of objects in each set. Suppose you are told that in a group of people there are 8 who run at least once a week and 6 who bike at least once a week. Can you conclude from this that there are \(8+6=14\) people who run or bike once a week? No, there is not enough information for such a conclusion. It may be that everyone that bikes also runs in which case there are only 8 people that run or bike once a week, not 14.

What we want to do is extend the sum rule to the case where we have a collection of sets with some elements appearing in more than one set. The simplest example has 2 sets as shown in the following figure.

Two Sets

Set \(A_1\) has 7 elements, \(A_2\) has 5 elements and the 2 sets have elements, 8 and 4, in common. If we sum the number of elements in each set then the elements they have in common will be counted twice. So the number they have in common has to be subtracted. The number of elements in \(A_1\) or \(A_2\) is then 7+5-2=10. To get a general formula for two sets, let \(|A_i|\) be the number of elements in set \(A_i\) then the number of elements in either set \(A_1\) or set \(A_2\) is given by:

\[|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\]

where \(|A_1\cap A_2|\) is the number of elements in both sets \(A_1\) and \(A_2\) i.e. the number of elements in the intersection of the 2 sets.

To extend this to 3 sets we need not just the number of elements in 2 sets at once but also the number of elements in 3 sets at once. The following figure shows an example.

Three Sets

It is similar to the 2 set example but now there is a third set \(A_3\) with 5 elements. \(A_3\) has 2 elements in common with both \(A_1\) and \(A_2\) and there is one element that is common to all 3 sets. If you sum the elements in all 3 sets then you will count elements 5, 7, and 8 twice and element 4 three times. Subtracting intersections between pairs of sets will zero out element 4 completely since it appears in 3 intersections. Element 4 is added back by adding the number of elements in the intersection of all 3 sets. The general formula for 3 sets is:

\[|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3|\]

In general, to count the number of elements in \(n\) sets we have the following formula:

\[\tag{80}|A_1\cup A_2\cup\cdots A_n|=\sum_{i=1}^n(-1)^{i-1}\sum_{j_1,j_2,\cdots,j_i}|A_{j_1}\cap A_{j_2}\cap \cdots A_{j_i}|\]

where the inner summation is over all \(i\) element subsets of \((1,2,\ldots,n)\). To prove this formula you only have to show that any element in the union contributes a 1 to the summation on the right hand side. We will sketch the proof but it can easily be skipped without loss of continuity or increase in confusion. Take an element \(x\) of the union that is a member of \(s\) of the sets. The \(|A_i|\) terms will contribute a \(\binom{s}{1}=s\) factor when counting the element. There will be \(\binom{s}{2}\) factor from the \(|A_i\cap A_j|\) terms, a \(\binom{s}{3}\) factor from the \(|A_i\cap A_j\cap A_k|\) terms and so on. The count for \(x\) is then equal to:

\[\tag{90}\binom{s}{1}-\binom{s}{2}+\binom{s}{3}-\cdots-(-1)^s\binom{s}{s}\]

You can see that this equation is always equal to 1 by comparing it to the expansion of \((y-1)^s\)

\[(y-1)^s=y^s-\binom{s}{1}y^{s-1}+\binom{s}{2}y^{s-2}-\binom{s}{3}y^{s-3}+\cdots+(-1)^s\binom{s}{s}\]

If you subtract this equation from 1 and set \(y=1\) you get equation 90. This means equation 90 is equal to \(1-(1-1)^s=1\) and it completes the proof.

An interesting application of equation 80 is counting the number of derangements. A derangement is a permutation of the numbers \(1,2,\ldots,n\) where no number equals its order in the permutation i.e. none of the numbers stays in the same position. When \(n=2\) the only derangement is \(2,1\). When \(n=3\) there are 2 derangements: \(2,3,1\) and \(3,1,2\). So for general \(n\) how many derangements are there? First let’s calculate how many permutations leave at least one number in fixed position. Let \(A_i\) be the set of permutations that leave the number \(i\) fixed. With \(i\) fixed, the other numbers can be permuted in \((n-1)!\) ways so this is the size of \(A_i\). The sum of the sizes of all the \(A_i\) is then equal to \(n(n-1)!=n!\). The set of permutations that leave both i and j fixed is \(A_i\cap A_j\). With \(i\) and \(j\) fixed the other numbers can be permuted in \((n-2)!\) ways so this is the size of \(A_i\cap A_j\). There are \(\binom{n}{2}\) ways to fix a pair of numbers so summing them all up gives

\[\binom{n}{2}(n-2)!=\frac{n!}{2!}\]

Likewise the contribution from 3 fixed numbers is

\[\binom{n}{3}(n-3)!=\frac{n!}{3!}\]

and so on. Putting all this into equation 80 gives the number of permutations with at least one fixed number.

\[n!\left[\frac{1}{1!}-\frac{1}{2!}+\frac{1}{3!}-(-1)^n\frac{1}{n!}\right]\]

The number of derangements is the total number of permutations, \(n!\), minus this number. Call \(D_n\) the number of derangements then

\[D_n = n!\sum_{i=0}^n\frac{(-1)^i}{i!}\]

To find the probability that a random permutation is a derangement divide both sides of the equation by \(n!\)

\[\frac{D_n}{n!} = \sum_{i=0}^n\frac{(-1)^i}{i!}\]

The sum on the right hand side of this equation converges to \(e^{-1}=0.367879\) as \(n\) goes to infinity. This means that for large \(n\) the probability of a random permutation being a derangement is about \(37\%\).