Notes: Counting functions.

Let f: K → N denote a function from a set K to a set N: to each element x ∈ K corresponds an element f(x) ∈ N. We say f “maps” x to f(x); sometimes we leave the f tacit and say that x maps to f(x).

We call f injective if distinct elements of K map to distinct elements of N: for all x, y ∈ K with x ≠ y, f(x) ≠ f(y).

We call f surjective if every element of N is mapped to by some element (or elements) of K: for all y ∈ N there exists x ∈ K with y = f(x).

We call f bijective if it is both injective and surjective. This says every element y in N is f(x) for one and only one element x ∈ K. For y ∈ N we may define g(y) to be this unique element x and thus construct a function g: N → K which is a left and right inverse to f. In other words g(f(x)) = x for all x ∈ K and f(g(y)) = y for all y ∈ N. Conversely if such an inverse exists then f is bijective. Indeed, if g(f(x)) = x for all x ∈ K then f must be injective since f(x) determines x, while if f(g(y)) = y for all y ∈ N then f must be surjective since g(y) is an element that maps (via f) to y.

One fundamental technique we use in combinatorics is to prove that two sets have the same number of elements by finding a bijection f between them. Frequently we will prove f is a bijection by finding its inverse g. Keep in mind that in such a proof we must check both directions: that g is a left and also a right inverse.

In these notes we are going to count functions f: K → N from a finite set K with |K| = k elements to N with |N| = n elements. Our intention is to explain within one concise framework the significance of the most basic enumeration problems of combinatorics: enumeration of permutations and combinations of sets and “multisets”, as well as of partitions of sets and of numbers, which we have already explored individually.

This framework is called the “12-fold way” and it uses two ideas to get various types of enumeration problems from the counting of functions f: K → N.

The first idea is to consider different restrictions on the functions f. Thus we may count all functions, or only injective functions, or only surjective functions. Note that we don’t need to make a count of bijective functions separately. For f can only be bijective when n = k, and then f is bijective iff f is injective iff f is surjective, so we can use enumerations of injective or surjective functions to cover this case.

The second idea, subtler than the first, is not just to count functions individually, but to group them together by regarding two functions as “the same” if they differ only by rearranging the elements of K, or of N, or both. Thus if we say that we consider the elelements of K indistinguishable, it means that two functions are to count as the same if one can be converted into the other by permuting the elements of K. Otherwise we consider the elements of K to be distinguished. We make similar definitions for N.

To understand these ideas it is best to consider their meaning more informally.

If K and N both have distinguished elements, then we are just counting functions individually.

If K has indistinguishable elements, then the relevant information about f is just: how many elements of K map to each element of N. For instance, suppose K = {w, x, y, z}, N = {a, b}, and f and g look like this:

Then we are not to count f and g as different, for if we changed the names of w, x, y, z to w, z, x, y, g would now map the way f did before. What can’t be changed by changing the names of elements in K is just the fact that f and g each map three elements to a and one to b. If N also had indistinguishable elements here, it wouldn’t even matter which of a and b got three elements and which got one. Then the only relevant information would be what numbers occur and how often: here 3 once and 1 once.

If N has indistinguishable elements, the relevant information about f is how it partitions K, that is, which elements of K map to the same element of N and which map to different ones. For instance these two functions would count as the same

because both partition K into {w, y} and {x, z}.

Now we have the 12 “ways” of counting functions in the 12-fold way. Each of K and N can have either distinguished or indistinguishable elements, for four possibilities. Within each of these we may count injective, surjective, or all functions, for a total of 12 different enumeration problems. Here is the table that results, followed by some commentary.

(Note: “N dist.” means the elements of N are distinguishable from one another; “N ind.” means that they are not. Similarly for K.)

Part I: f : K → N injective:

N dist. N indist.
K dist. (n)_{k}  \begin{matrix}1 & if k ≤ n \\ 0 & if k > n \end{matrix}
K ind. \binom{n}{k}  \begin{matrix}1 & if k ≤ n \\ 0 & if k > n \end{matrix}

K dist., N dist.: (n)_{k} = n(n − 1) ⋯ (n − k + 1) is the falling factorial; in Brualdi it is written as [n]_{k} or P (n, k). Injections from a k-element set of indistinguishable elements to the set N are really the same thing as k-permutations of the set N.

K ind., N dist.: \binom{n}{k} = \frac{(n)_{k}}{k!} = \frac{n!}{k!(n−k)!} is the binomial coefficient “n choose k”. Brualdi also writes it as C(n, k). Since K has indistinguishable elements, the order of the values of f (call them f_{1}, f_{2}, ..., f_{k}) is immaterial and we are counting k-combinations from N, that is, subsets of N with k elements.

K dist., N ind.: If k > n, there are no such functions. If k ≤ n, then such functions exist, but they may all be obtained from one another by re-labelling.

K ind., N ind.: Ditto.

Part II: f : K → N unconstrained:

N dist.  N indist.
K dist. n^{k} S(k, 1) + S(k, 2) + ... + S(k, n)
K ind. \binom{n}{k}  p_{1}(k) + p_{2}(k) + ... + p_{n}(k)

K dist., N dist.: n^{k} is the number of functions from K to N since each of the k values f(x) for x ∈ K can be chosen independently in n ways. Such functions are essentially the same as k-permutations from N with unlimited repetition.

K ind., N dist.: \binom{n}{k} is read “n multichoose k”. This is the number of k-combinations with unlimited repetition from N, since when K has indistinguishable elements the order in which f_{1}, f_{2}, ..., f_{k} occur is immaterial. Brualdi Theorem 3.5.1 expresses \binom{n}{k} as \binom{n+k−1}{k}. It is equal to the number of n-tuples of non-negative integers summing to k.

For explanations of the other two entries in the table, see below.

Part III: f : K → N surjective:

N dist. N indist.
K dist. n! S(k, n) S(k, n)
K ind. \binom{n}{k−n}  p_{n}(k)

K dist., N ind.: S(k, n) is a Stirling number of the second kind, and equals the number of partitions of a k-element set into n blocks. That’s what we’re counting here with N having indistinguishable elements. When f is not surjective, as in Part II, not all elements of N correspond to blocks – only those that actually are mapped to by f. Then we are counting partitions with at most n blocks, giving the entry S(k, 1) + ... + S(k, n) in Part II.

K ind., N ind.: p_{n}(k) is defined as the number of partitions of the integer k into n positive parts: they are the sizes of the blocks of the partition of the set K. Since K has indistinguishable elements the actual set-partition is lost; only the block sizes count. The reasoning for p_{1}(k) + ... + p_{n}(k) in Part II is like that for S(k, 1) + ... + S(k, n) given above.

K dist., N dist.: Since f is surjective, each partition of N into k blocks gives rise to n! different functions, by permuting the elements of N. Therefore the number of such functions is n! S(k, n). Note that this reasoning does not apply in Part II; for there, f need not be surjective, and if there are elements of N not mapped to by f, permuting such elements does not affect f.

K ind., N dist.: Such maps correspond to n-tuples of positive integers summing to k (cf. the corresponding case in Part II). By subtracting 1 from each part, we obtain a n-tuple of non-negative integers summing to k − n, and the number of such n-tuples is \binom{n}{k−n}.