Discrete Mathematics and Proof

Inclusion-exclusion for three or more sets, and derangements

Several groups overlap in every possible way. How do you count what is in at least one of them, or in none?

You need

CombinationsAlgebra 2 Venn diagrams and counting a unionAlgebra 2

Where you are 10 in Counting

Probability4

Counting10

▴ 1 above Combinations Combinations with repetition: stars and bars

Inclusion-exclusion for three or more sets, and derangements

Probability with counting formulas The fundamental counting principle ▾ Show all 10 (4 more)

When you reach for it

The two-set count handles “in A or in B”. Many questions involve three properties, or ten, or n: integers divisible by at least one of several numbers, arrangements in which at least one object stays where it was, functions that miss at least one value, solutions of an equation in which some variable is too large. In each case the single sets and their intersections are easy to count, while the union is not. Often the target is the opposite count, the elements with none of the properties, where each property names a kind of element to throw out.

Inclusion-exclusion turns the easy counts into the hard one: add the single sets, subtract the intersections of two, add back the intersections of three, and keep alternating.

The procedure

Day 1: three sets, then any number

Throughout, the sets are finite subsets of a universal set U.

Three sets. For finite sets A, B, C,

\begin{aligned} &\lvert A \cup B \cup C\rvert \\ &\quad = \lvert A\rvert + \lvert B\rvert + \lvert C\rvert \\ &\quad\quad - \lvert A \cap B\rvert - \lvert A \cap C\rvert - \lvert B \cap C\rvert \\ &\quad\quad + \lvert A \cap B \cap C\rvert \end{aligned}

Proof. Each term on the right counts certain elements once, with a plus or a minus sign. Take any element x of U and add up what x contributes. If x lies in none of the sets, it is in no term and contributes 0, which is right, since it is not in the union. If x lies in exactly one set, it appears in one single-set term and in no intersection: it contributes 1. If x lies in exactly two, say A and B but not C, it appears in \lvert A\rvert, \lvert B\rvert and \lvert A \cap B\rvert and nowhere else: 1 + 1 - 1 = 1. If x lies in all three, it appears in all three single terms, all three pair terms and the triple term: 3 - 3 + 1 = 1. So every element of the union is counted exactly once and every other element zero times. \square

Figure 1Each region is labeled with how many of the three sets contain it. The proof checks that every label from 1 to 3 leads to a net count of exactly 1.

An element in exactly j of the sets lies in \binom{j}{1} single sets, \binom{j}{2} pairwise intersections and \binom{j}{3} triple ones (Combinations):

j	single terms	pair terms	triple term	net count
1	1	0	0	1
2	2	1	0	1
3	3	3	1	1

Regions from totals. Three loops cut U into eight regions. Given the seven totals, fill them from the center outward: the center is \lvert A \cap B \cap C\rvert; each region in exactly two sets is a pairwise intersection minus the center; each region in exactly one set is that set minus its two pairwise intersections plus the center (the center was taken away twice); and “in none” is \lvert U\rvert minus the union.

Any number of sets. For finite sets A_1, \dots, A_n, let S_k be the sum of the sizes of all intersections of exactly k of them, one term for each k-element set I of indices:

S_k = \sum_{\lvert I\rvert = k} \Big\lvert \bigcap_{i \in I} A_i \Big\rvert

There are \binom{n}{k} terms in S_k. The principle of inclusion-exclusion states

\begin{aligned} &\lvert A_1 \cup \cdots \cup A_n\rvert \\ &\quad = S_1 - S_2 + S_3 - \cdots + (-1)^{n+1} S_n \end{aligned}

Proof. Again add up the contribution of one element x. An x in none of the sets is in no intersection and contributes 0. Otherwise let J be the set of indices i with x \in A_i, and let j = \lvert J\rvert \ge 1. The element x lies in \bigcap_{i \in I} A_i exactly when I \subseteq J, so S_k counts x once for each k-element subset of J, which is \binom{j}{k} times (zero times when k > j). The net contribution of x is

\begin{aligned} &\binom{j}{1} - \binom{j}{2} + \cdots + (-1)^{j+1}\binom{j}{j} \\ &\quad = 1 - \sum_{k=0}^{j} (-1)^k \binom{j}{k} \end{aligned}

By the binomial theorem, \sum_{k=0}^{j} (-1)^k \binom{j}{k} = (1 - 1)^j = 0 because j \ge 1. So each element of the union contributes exactly 1. \square

Counting none. The elements of U in none of the sets are U minus the union. Writing S_0 = \lvert U\rvert,

\begin{aligned} &\lvert U\rvert - \lvert A_1 \cup \cdots \cup A_n\rvert \\ &\quad = S_0 - S_1 + S_2 - \cdots + (-1)^n S_n \end{aligned}

In practice the sets come from properties: A_i is the set of elements of U with property i, and this sum counts the elements with none of the properties.

When the intersections are alike. If every intersection of k of the sets has the same size N_k, then S_k = \binom{n}{k} N_k, and the whole count is one short sum. Every count on Day 2 has this shape.

Day 2: upper bounds, onto functions, derangements

Upper bounds in stars and bars. The equation x_1 + \cdots + x_m = k has \binom{k + m - 1}{m - 1} solutions in nonnegative integers (Combinations with repetition: stars and bars). Now require every x_i \le c. Call a solution bad for i when x_i \ge c + 1, and let A_i be those solutions. For a set I of r indices, writing x_i = y_i + (c + 1) for each i \in I matches the solutions in \bigcap_{i \in I} A_i one to one with the nonnegative solutions of an equation with total k - r(c + 1). So that intersection has \binom{k - r(c+1) + m - 1}{m - 1} elements when k - r(c + 1) \ge 0, and none otherwise. Counting the solutions with no bad variable,

\sum_{r \ge 0} (-1)^r \binom{m}{r} \binom{k - r(c+1) + m - 1}{m - 1}

where r runs only while k - r(c + 1) \ge 0.

Onto functions. Let K and N be sets with k and n elements. There are n^k functions f : K \to N, one choice of value for each of the k elements (The fundamental counting principle). Such an f is onto unless it misses some y \in N. Let A_y be the functions that miss y. A function that misses every element of a set T of i elements is a function into N \setminus T, and there are (n - i)^k of those. So the number of onto functions K \to N is

\sum_{i=0}^{n} (-1)^i \binom{n}{i} (n - i)^k

Derangements. A permutation \sigma of \{1, 2, \dots, n\}, a bijection of the set to itself (Arrangements and factorials), is a derangement when \sigma(i) \ne i for every i: nothing stays in its place. Write D_n for their number. Let A_i be the permutations with \sigma(i) = i. Fixing every element of a set of k indices leaves a permutation of the other n - k elements, so each k-fold intersection has (n - k)! elements. Since \displaystyle \binom{n}{k}(n - k)! = \frac{n!}{k!},

\begin{aligned} D_n &= \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n - k)! \\ &= n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} \end{aligned}

n	D_n	n!
0	1	1
1	0	1
2	1	2
3	2	6
4	9	24
5	44	120
6	265	720
7	1854	5040
8	14{,}833	40{,}320

(D_0 = 1: the empty permutation moves nothing out of place, because there is nothing.) The ratio \displaystyle \frac{D_n}{n!} is the chance that a permutation chosen at random has no fixed point, and

\lim_{n \to \infty} \frac{D_n}{n!} = \frac{1}{e} \approx 0.367879

This is stated, not proved here: it rests on the series \displaystyle e^{-1} = \sum_{i \ge 0} \frac{(-1)^i}{i!} from calculus. Already at n = 7 the ratio \displaystyle \frac{1854}{5040} agrees with \displaystyle \frac{1}{e} to four decimal places.

Worked examples

Example 1

Day 1: three electives

A school has 90 students and three electives. 38 students take Botany, 32 take Calligraphy and 25 take Paleontology; 12 take Botany and Calligraphy, 10 Botany and Paleontology, 9 Calligraphy and Paleontology, and 4 take all three. How many take at least one elective? None? Exactly one? Exactly two?

Solution

Let B, C, P be the three sets. By the three-set formula,

\begin{aligned} \lvert B \cup C \cup P\rvert &= 38 + 32 + 25 \\ &\quad - 12 - 10 - 9 + 4 = 68 \end{aligned}

so 68 students take at least one and 90 - 68 = 22 take none. For the rest, fill the regions from the center outward. The center holds 4. The exactly-two regions are 12 - 4 = 8, 10 - 4 = 6 and 9 - 4 = 5. Botany only is 38 - 12 - 10 + 4 = 20, since the center sits inside both of Botany’s overlaps and was subtracted twice; likewise Calligraphy only is 32 - 12 - 9 + 4 = 15 and Paleontology only is 25 - 10 - 9 + 4 = 10.

Figure 2The 90 students of Example 1, filled in from the center outward.

Exactly one: 20 + 15 + 10 = 45. Exactly two: 8 + 6 + 5 = 19.

Check. 45 + 19 + 4 + 22 = 90.

Example 2

Day 1: multiples of 4, 6 or 9

How many integers from 1 to 600 are divisible by at least one of 4, 6, 9? How many by none?

Solution

Let A_d be the multiples of d in \{1, \dots, 600\}; there are \lfloor 600/d\rfloor of them. The singles are \lvert A_4\rvert = 150, \lvert A_6\rvert = 100 and \lvert A_9\rvert = 66, since 9 \cdot 66 = 594. An integer divisible by two numbers is divisible by their least common multiple and conversely, so the intersections are counted by least common multiples, not products: \operatorname{lcm}(4, 6) = 12, \operatorname{lcm}(4, 9) = 36, \operatorname{lcm}(6, 9) = 18, giving 50, 16 and 33. For all three, \operatorname{lcm}(4, 6, 9) = 36, giving 16 again: every multiple of 36 is already a multiple of 6. So

150 + 100 + 66 - 50 - 16 - 33 + 16 = 233

are divisible by at least one, and 600 - 233 = 367 by none.

Check. Up to 36 the same count gives 9 + 6 + 4 - 3 - 1 - 2 + 1 = 14, and the list 4, 6, 8, 9, 12, 16, 18, 20, 24, 27, 28, 30, 32, 36 has 14 entries.

Example 3

Day 1: gloves with no matching pair

A drawer holds 6 pairs of gloves, all 12 gloves different. In how many ways can 4 gloves be chosen so that no complete pair is among them?

Solution

There are \binom{12}{4} = 495 choices in all. Let A_i be the choices containing both gloves of pair i, for i = 1, \dots, 6. A choice in A_i is those two gloves plus 2 of the other 10: \binom{10}{2} = 45, the same for every i. A choice in A_i \cap A_j is both pairs and nothing else: 1 way, for each of the \binom{6}{2} = 15 pairs of indices. Three complete pairs need 6 gloves, so every triple intersection is empty. Counting the choices in none of the A_i,

495 - 6 \cdot 45 + 15 \cdot 1 = 240

Check. Directly, a choice with no complete pair takes one glove from each of 4 different pairs: \binom{6}{4} \cdot 2^4 = 15 \cdot 16 = 240.

Example 4

Day 2: an equation with an upper bound

How many solutions in nonnegative integers does x_1 + x_2 + x_3 = 15 have with every x_i \le 6?

Solution

Without the bound there are \binom{17}{2} = 136 solutions. A solution is bad for i when x_i \ge 7. Writing x_1 = y_1 + 7 turns the solutions bad for 1 into the nonnegative solutions of y_1 + x_2 + x_3 = 8, of which there are \binom{10}{2} = 45, and the same holds for each of the 3 variables. Bad for two variables leaves total 15 - 14 = 1: \binom{3}{2} = 3 solutions, for each of \binom{3}{2} = 3 pairs. Bad for all three would need 21 > 15. So

136 - 3 \cdot 45 + 3 \cdot 3 = 10

Check. Every solution is a rearrangement of 6 + 6 + 3 (3 orders), 6 + 5 + 4 (6 orders) or 5 + 5 + 5 (1 order): 10 in all.

Example 5

Day 2: strings that use every letter

How many strings of length 6 over the letters a, b, c use each letter at least once?

Solution

A string is a function from the six positions to \{a, b, c\}, and using every letter means the function is onto. So k = 6, n = 3: there are 3^6 = 729 strings, 2^6 = 64 miss a given letter, 1^6 = 1 misses a given pair of letters, and none misses all three. Hence

729 - 3 \cdot 64 + 3 \cdot 1 - 0 = 540

Check. With k = n = 3 the formula gives 27 - 3 \cdot 8 + 3 - 0 = 6 = 3!, as it must: an onto function from a 3-set to a 3-set is a bijection.

Example 6

Day 2: a gift exchange

Mael writes the names of seven friends, himself included, on slips; each friend draws one slip at random. How many drawings leave nobody with their own name? What fraction of all drawings is that? How many drawings give exactly two people their own names?

Solution

A drawing assigns each person a name, each name used once: a permutation of the seven. Nobody drawing their own name is a derangement, so the count is

\begin{aligned} D_7 &= 5040 - 5040 + 2520 - 840 \\ &\quad + 210 - 42 + 7 - 1 = 1854 \end{aligned}

Out of 7! = 5040 drawings, that is a fraction \displaystyle \frac{1854}{5040} \approx 0.3679, close to \displaystyle \frac{1}{e}. For exactly two, choose the two who draw their own names, \binom{7}{2} = 21 ways; the other five must then all miss, which is a derangement of five, D_5 = 44 ways. So 21 \cdot 44 = 924 drawings.

Example 7

Day 2: Euler’s phi function

The phi function \varphi(n) counts the integers a with 1 \le a \le n and \gcd(a, n) = 1 (Introductory number theory). Find \varphi(300) by inclusion-exclusion.

Solution

Since 300 = 2^2 \cdot 3 \cdot 5^2, an integer shares a factor greater than 1 with 300 exactly when it is divisible by 2, 3 or 5. Count the integers from 1 to 300 divisible by none of them. The three primes are distinct, so an integer is divisible by several of them exactly when it is divisible by their product:

\begin{aligned} \varphi(300) &= 300 - (150 + 100 + 60) \\ &\quad + (50 + 30 + 20) - 10 \\ &= 80 \end{aligned}

The same sum factors as \displaystyle 300 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 80, a factor \displaystyle 1 - \frac{1}{p} for each prime p dividing 300, which is how the product formula for \varphi arises.

Boundaries

Finite sets. Every term is a number of elements, so every set involved must be finite.

All the intersections are needed. The formula uses every S_k. Leaving off the last terms does not give the exact count, and the singles with the pairs alone do not fix the union of three sets.

“None” needs a universal set. S_0 = \lvert U\rvert must be stated before “none” has a meaning.

Bounded stars and bars. The bad-variable shift needs nonnegative variables. A lower bound x_i \ge a is removed first by writing x_i = a + y_i. An intersection whose total k - r(c+1) is negative is empty, not a negative binomial coefficient.

Onto functions and derangements count labeled things. The surjection formula treats every element of K and of N as distinct; identical objects into boxes is a different count. A derangement is a permutation of one set to itself; “nobody gets their own” has a meaning only when each object has exactly one place of its own.

The limit \displaystyle \frac{1}{e} is stated, not proved, and it describes \displaystyle \frac{D_n}{n!} as n grows; for n = 1, 2, 3 the ratio is 0, 0.5 and about 0.333.

Where this goes next

The alternating sums met here are identities in disguise: the surjection count gives 0 when k < n and n! when k = n (Exercise 25), facts proved by meaning rather than algebra in Combinatorial proof: counting one set two ways, while the sign pattern \binom{j}{0} - \binom{j}{1} + \cdots = 0 says that the signed entries of each row of Pascal’s triangle cancel. The phi function returns in number theory, along with its product formula. In probability, dividing every count by \lvert U\rvert gives the chance that none of several events happens, the setting of At least one problems.

Exercises

Day 1: three sets

\lvert A\rvert = 20, \lvert B\rvert = 18, \lvert C\rvert = 15, \lvert A \cap B\rvert = 7, \lvert A \cap C\rvert = 5, \lvert B \cap C\rvert = 6 and \lvert A \cap B \cap C\rvert = 3. Find \lvert A \cup B \cup C\rvert.
\lvert A \cup B \cup C\rvert = 45, \lvert A\rvert = 25, \lvert B\rvert = 22, \lvert C\rvert = 19, \lvert A \cap B\rvert = 10, \lvert A \cap C\rvert = 9 and \lvert B \cap C\rvert = 8. Find \lvert A \cap B \cap C\rvert and the number of elements in A only.
In a universal set of 100 elements, \lvert X\rvert = 37, \lvert Y\rvert = 40, \lvert Z\rvert = 21, \lvert X \cap Y\rvert = 14, \lvert X \cap Z\rvert = 8, \lvert Y \cap Z\rvert = 7 and \lvert X \cap Y \cap Z\rvert = 3. Fill in all eight regions, and find how many elements lie in exactly one set, in exactly two, and in none.

Day 1: counting numbers, strings and choices

How many integers from 1 to 1000 are divisible by at least one of 6, 10, 15?
How many integers from 1 to 2000 are divisible by none of 3, 7, 11?
How many strings of 5 decimal digits (leading zeros allowed) contain each of the digits 1, 2, 3 at least once?
Write out the inclusion-exclusion formula for \lvert A \cup B \cup C \cup D\rvert. How many terms does it have, and how many does the formula for n sets have?
From the drawer of 6 different pairs of gloves, in how many ways can 5 gloves be chosen with no complete pair among them? Check your answer by a direct count.

Day 1: explaining the count

Mael gives these counts for three subsets of a 70-element set: \lvert A\rvert = 20, \lvert B\rvert = 30, \lvert C\rvert = 25, \lvert A \cap B\rvert = 12, \lvert A \cap C\rvert = 11, \lvert B \cap C\rvert = 9, \lvert A \cap B \cap C\rvert = 2. Show that they cannot all be right, even though the union they give is less than 70.
Prove that the number of elements in exactly one of A, B, C is \lvert A\rvert + \lvert B\rvert + \lvert C\rvert, minus 2(\lvert A \cap B\rvert + \lvert A \cap C\rvert + \lvert B \cap C\rvert), plus 3\lvert A \cap B \cap C\rvert.

Day 2: upper bounds

How many solutions in nonnegative integers does x_1 + x_2 + x_3 + x_4 = 12 have with every x_i \le 4?
Three dice of different colors are rolled. In how many of the 216 outcomes is the total 12?
How many strings of 3 decimal digits, from 000 to 999, have digit sum 20?

Day 2: onto functions

How many functions from a 5-element set onto a 2-element set are there?
How many functions from a 7-element set onto a 3-element set are there?
How many functions from \{1, 2, 3, 4, 5\} onto \{1, 2, 3, 4\} are there? Check by noting that exactly one value must be taken twice.
Evaluate the surjection sum for k = 3 and n = 4, and say why the result is right.

Day 2: derangements and the phi function

In a gift exchange of 8 people, how many drawings leave nobody with their own name, and what fraction of all drawings is that, to four decimal places?
In a gift exchange of 6 people, how many drawings give exactly one person their own name?
In a gift exchange of 6 people, how many drawings give at least one person their own name?
Compute \displaystyle \frac{5!}{e}, \displaystyle \frac{6!}{e} and \displaystyle \frac{7!}{e} to two decimal places and compare each with D_5, D_6, D_7.
Find \varphi(84) by inclusion-exclusion.
How many integers from 1 to 210 are divisible by at least one of 2, 3, 5, 7?

Day 2: reasoning

Prove that \sum_{k=0}^{j} (-1)^k \binom{j}{k} = 0 for every integer j \ge 1 without the binomial theorem, by pairing the subsets of \{1, \dots, j\} that contain 1 with those that do not.
Explain, from what the sum counts, why \sum_{i=0}^{n} (-1)^i \binom{n}{i}(n - i)^k equals 0 when k < n and equals n! when k = n.

Answers

38. 20 + 18 + 15 - 7 - 5 - 6 + 3 = 38.
\lvert A \cap B \cap C\rvert = 6 and A only holds 12. From 45 = 66 - 27 + t, t = 6; then A only is 25 - 10 - 9 + 6 = 12.
Center 3; X \cap Y only 11, X \cap Z only 5, Y \cap Z only 4; X only 37 - 14 - 8 + 3 = 18, Y only 40 - 14 - 7 + 3 = 22, Z only 21 - 8 - 7 + 3 = 9. The union is 98 - 29 + 3 = 72, so none holds 28. Exactly one: 49; exactly two: 20. Check: 49 + 20 + 3 + 28 = 100.
266. Each pair and the triple have least common multiple 30, with 33 multiples: 166 + 100 + 66 - 3 \cdot 33 + 33 = 266.
1040. The union is 666 + 285 + 181 - 95 - 60 - 25 + 8 = 960 (multiples of 21, 33, 77, 231 in the subtracted and added terms), and 2000 - 960 = 1040.
4350. Let A_d be the strings with no digit d: 9^5 = 59{,}049 each, 8^5 = 32{,}768 for each pair, 7^5 = 16{,}807 for all three. Then 100{,}000 - 3 \cdot 59{,}049, plus 3 \cdot 32{,}768, minus 16{,}807, gives 4350.
Four single terms added, six pairwise intersections subtracted, four triple intersections added, one fourfold intersection subtracted: 15 terms. For n sets there is one term per nonempty set of indices, 2^n - 1 terms.
192. \binom{12}{5} - 6\binom{10}{3} + 15\binom{8}{1} = 792 - 720 + 120 = 192; three pairs would need 6 gloves. Directly, \binom{6}{5} \cdot 2^5 = 192.
A only would hold 20 - 12 - 11 + 2 = -1 elements, which is impossible. The union, 75 - 32 + 2 = 45, raises no alarm; only the regions do.
An element in exactly j of the sets contributes j - 2\binom{j}{2} + 3\binom{j}{3}, which is 1 for j = 1, 2 - 2 = 0 for j = 2 and 3 - 6 + 3 = 0 for j = 3, and an element in none contributes 0. So the expression counts exactly the elements in one set. With Exercise 3: 98 - 2 \cdot 29 + 9 = 49.
35. \binom{15}{3} - 4\binom{10}{3} + 6\binom{5}{3} = 455 - 480 + 60 = 35; three bad variables would need 15 > 12.
25. With y_i = x_i - 1, count y_1 + y_2 + y_3 = 9 with y_i \le 5: \binom{11}{2} - 3\binom{5}{2} = 55 - 30 = 25.
36. \binom{22}{2} - 3\binom{12}{2} + 3\binom{2}{2} = 231 - 198 + 3 = 36.
30. 2^5 - 2 \cdot 1^5 = 30: every function except the two constant ones.
1806. 3^7 - 3 \cdot 2^7 + 3 \cdot 1^7 = 2187 - 384 + 3 = 1806.
240. 4^5 - 4 \cdot 3^5 + 6 \cdot 2^5 - 4 \cdot 1^5 is 1024 - 972 + 192 - 4 = 240. Directly: choose the two elements sharing a value, \binom{5}{2} = 10, then match the four groups to the four values, 4! = 24: 240.
0. 64 - 4 \cdot 27 + 6 \cdot 8 - 4 \cdot 1 + 0 = 0, as it must be: three elements have at most three values, so no function from them is onto a 4-element set.
D_8 = 14{,}833, and \displaystyle \frac{14{,}833}{40{,}320} \approx 0.3679.
264. Choose the one person, 6 ways; the other five are deranged, D_5 = 44: 6 \cdot 44 = 264.
455. 720 - D_6 = 720 - 265 = 455.
44.15, 264.87, 1854.11. Rounded to the nearest integer they are 44, 265, 1854, which are D_5, D_6, D_7.
\varphi(84) = 24. 84 = 2^2 \cdot 3 \cdot 7, so count 1 to 84 divisible by none of 2, 3, 7: 84 - (42 + 28 + 12) + (14 + 6 + 4) - 2 = 24.
162. S_1 = 105 + 70 + 42 + 30 = 247, S_2 = 35 + 21 + 15 + 14 + 10 + 6 = 101, S_3 = 7 + 5 + 3 + 2 = 17, S_4 = 1: 247 - 101 + 17 - 1 = 162.
For a subset I not containing 1, pair it with I \cup \{1\}. Every subset lies in exactly one such pair, and the two sizes differ by one, so the pair contributes (-1)^{\lvert I\rvert} + (-1)^{\lvert I\rvert + 1} = 0 to \sum_{I} (-1)^{\lvert I\rvert}. Hence that sum is 0. Grouping the subsets by size, there are \binom{j}{k} of size k, so the sum equals \sum_{k=0}^{j} (-1)^k \binom{j}{k}. The pairing needs the element 1, which is why j \ge 1; for j = 0 the sum is 1.
The sum counts the functions from a k-set onto an n-set. When k < n, a function takes at most k values, fewer than n, so none is onto and the count is 0. When k = n, an onto function takes all n values on n elements, so no two elements share a value (The pigeonhole principle): it is a bijection, and there are n! bijections between two n-element sets.