Onto Functions: Stirling Numbers of the Second Kind
Onto Functions A function f: A -> B is onto, or surjective, if f(A) = B (the range is equal to the codomain, all of the elements in the codomain are used in f), where for every b ∈ B, there is at least one a ∈ A such that f(a) = b.
Example The function f: ℝ -> ℝ defined by f(x) = x³ is an onto function. If r is any real number in the codomain of f, then the real number ³√r is in the domain of f and f(³√r) = (³√r)³ = r. Therefore, the codomain of f = ℝ = the range of f, and so the function f is onto.
Example The function g: ℝ -> ℝ defined by g(x) = x² for each real number x is not an onto function. No negative real number appears in the range of g despite negative numbers appearing in the codomain of g. For -9 to be in the range of g, then there must exist some real number r such that g(r ) = r² = -9, which is impossible if only real numbers are considered. The range of g is then [0,∞), and so if g was instead g: ℝ -> [0,∞) defined by g(x) = x², then g would be an onto function.
Example Consider the function f: ℤ -> ℤ where f(x) = 3x + 1 for each x ∈ ℤ. The range of f is {...,-8,-5,-2,1,4,7,...} ⊂ ℤ, and so f is not an onto function. The integer 8 is not in the range of f, even though 3x + 1 = 8 can easily solve for x to be 7/3, however 7/3 ∉ ℤ. However, if f was instead f: ℚ -> ℚ defined as f(x) = 3x + 1 for x ∈ ℚ, or f was instead f: ℝ -> ℝ, defined as f(x) = 3x + 1 for x ∈ ℝ, then both functions are onto. Furthermore, regardless of the domain and codomain, the function f is one-to-one.
Example Let A = {1,2,3,4} and B = {x,y,z}. Then f₁ = {(1,z), (2,y), (3,x), (4,y)} and f₂ = {(1,x), (2,x), (3,y), (4,z)} are both functions from A onto B. However, the function g = {(1,x), (2,x), (3,y), (4,y)} is not onto, because g(A) = {x,y} ⊂ B.
If A,B are finite sets, then for f: A -> B to be onto, |A| ≥ |B|. (the number of elements in the domain must be greater than or equal to the number of elements in the codomain)
Example Let A = {x,y,z} and B = {1,2}. Then all of the functions f: A -> B are onto except the two functions f₁ = {(x,1), (y,1), (z,1)} and f₂ = {(x,2), (y,2), (z,2)}, which are all of the possible functions where only one variable in B is an image of each element in A under f. These two functions are called constant functions. Therefore, the total amount of onto functions from A to B in this case is (total number of functions) – (total number of functions not onto) = |B||A| - |{f₁,f₂}| = 2³ – 2.
In general, if |A| ≥ 2 and |B| = 2, then there are 2ᵐ – 2 onto functions from A to B.
Example Let A = {w,x,y,z} and B = {1,2,3}. Then there are 3⁴ functions from A to B. Considering the subsets of B of size 2, then there are 2⁴ functions from A to {1,2}, 2⁴ functions from A to {2,3}, and 2⁴ functions from A to {1,3}. Therefore, there is a total of 3(2⁴) = C(3,2)(2⁴) functions from A to be that are not onto. However, not all of the C(3,2)(2⁴) functions are distinct, and so over counting occurs. Therefore, C(3,2)(2⁴) is subtracted from the total number of functions from A to B. Additionally, the subsets of B of the constant functions are also added to C(3,2)(2⁴), since they are included as functions that are not onto. Therefore, the total number of functions from A to B that are onto is 3⁴ – C(3,2)(2⁴) + 3, which can be rewritten as C(3,3)(3⁴) - C(3,2)(2⁴) + C(3,1)(1⁴) = 36.
Number of Onto Functions In general, the number of onto functions from finite sets A to B is calculated using the following formula:
Note that the upper limit is usually |B| - 1.
Example Let A = {1,2,3,4,5,6,7} and B = {w,x,y,z}. Then the following is the total number of onto functions from A to B:
Example At the CH Company, Joan has a secretary, Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can Joan assign the accounts such that each assistant works on at least one account and Teresa's work includes the most expensive account? There are two disjoint cases that will use the rule of sum later: Case 1: If Teresa works only on the most expensive account, then the other six accounts can be distributed among the three administrative assistants in the following number of ways:
Case 2: If Teresa does more than just the most expensive account, the assignments for each of the three assistants and her is calculated as the following:
Then, by the rule of sum, the assignments can be given under the conditions in 540 + 1560 = 2100 ways.
Example Seven unrelated people enter the lobby of a building which has four additional floors, and they all get on an elevator. What is the probability that the elevator must stop at every floor in order to let passengers off? The sample space in this case is the number of possible ways seven people can each select one of the four floors, which is 4⁷ =16384 ways. (the number of functions f: A -> B, |A| = 7, |B| = 4) The event concerned contains 8400 of those possible ways. (the number of onto functions from A to B given f: A -> B, |A| = 7, |B| = 4) Therefore, the probability that the elevator must stop at every floor is 8400/16384 = 0.5127.
Example To prove that for every positive integers m,n, with m < n, the following is true:
Notice how this summation is the same summation for finding the number of onto functions from A to B. Let m = |A| and n = |B|. It was stated for all positive integers m,n, with m < n, so then |A| < |B|, which means the elements in B will not all be in the range of A, since there are less elements in A than in B. This is why the summation is 0. There are 0 onto functions from A to B given |A| < |B|.
Bijections and Number of Bijections When a function f: A -> B is both one-to-one and onto, then the function is called a bijection.
When a function is a bijection, the cardinalities of the domain and the codomain are equal. Since the function is one-to-one, the elements of B can only be used once, and so for the first element of A, there are |B| number of choices. For the second element of A, there are |B| - 1 number of choices. This pattern continues until all of the elements of A are considered. And since |A| = |B|, all of B's elements are also considered.
Therefore, the number of bijections a function has if it is one-to-one and onto is |B|!.
The following example will introduce the concept of a Stirling number of the second kind:
Example Let A = {a,b,c,d} and B = {1,2,3}. Then, using the above formula, there are 36 onto functions from A to B. Equivalently, this means there are 36 ways to distribute four distinct objects into three distinguishable yet identical containers, leaving no container empty and the location of each object doesn't matter. Among the 36 distributions, for one distribution there are six possible arrangements for this distribution: 1) {a,b}₁ {c}₂ {d}₃ 2) {a,b}₁ {d}₂ {c}₃ 3) {c}₁ {a,b}₂ {d}₃ 4) {c}₁ {d}₂ {a,b}₃ 5) {d}₁ {a,b}₂ {c}₃ 6) {d}₁ {c}₂ {a,b}₃ Note that there are 5 other distributions that each have six arrangements each, which totals 36 ways to distribute the objects. Where the notation, such as {c}₂, indicates that c is in the second container (the container is labeled with 2). Since there are 3 containers, there is a total of 3! = 6 arrangements for each possible distribution when each container is labeled. When the labels of the containers are removed, then arrangements of the containers does not matter, and so there are 36/3! = 6 ways to distribute the distinct objects a,b,c,d among three identical containers, with no container left empty.
Stirling Numbers of the Second Kind From the above example, it was found that, for m ≥ n, the following is the number of ways to distribute m distinct objects into n numbered but identical containers with no container left empty:
When the numbers on the container are removed so that each container is also identical in appearance, then one distribution into the n nonempty identical containers corresponds with n! such distributions when the containers were labeled.
Therefore, the number of possible ways to distribute the m distinct objects in n identical non-distinguishable containers, with no container left empty, is the following:
This formula is also known as a Stirling number of the second kind, denoted as S(m,n).
Note that, for the function f: A -> B with |A| = m ≥ n = |B|, then the number of onto functions from A to B is n!S(m,n).
The following table lists some Stirling numbers of the second kind:
Example For m ≥ n, then the following is the number of possible ways to distribute m distinct objects into n identical containers, where empty containers are allowed:
From the above table of Stirling numbers in the fourth row, there are 1 + 7 + 6 = 14 ways to distribute four distinct objects into three containers, with some container(s) possible empty.
Partitioning of a Set A partition of a set X into r parts is a collection of subsets X₁, X₂, ..., Xᵣ ⊆ X such that the following is true:
A partition can also be viewed as a function f: X -> {1,2,...,r}, where f(y) = r if and only if y ∈ Xᵢ. Such functions are ordered partitions.
If the ordered partition f: X -> {1,2,...,r} is onto, where |X| = m ≤ r = |{1,2,...,r}|, then f partitions X into r non-empty subsets, where S(m,r) calculates the number of possible partitions from an m-set X onto r non-empty subsets.
Note that r!S(m,r) is the number of onto functions from an m-set X to an r-set.
PDF reference: 286/917
a) Let A = {1,2,3,4} and B = {w,x,y,z}.
A function that is neither one-to-one nor onto is a function that contains the elements in A and not all elements in B such that some repeat.
Example: {(1,w), (2,w), (3,y), (4,y)}
b) Let A = {1,2,3,4} and B = {v,w,x,y,z}.
A function that is one-to-one but not onto is a function that contains the elements in A and not all elements in B such that there are no repeats.
Example: {(1,v), (2,w), (3,x), (4,y)}
c) Let A = {1,2,3,4,5} and B = {w,x,y,z}.
A function that is onto but not one-to-one is a function that contains the elements in A and all elements in B such that there are repeats.
Example: {(1,w), (2,x), (3,y), (4,z), (5,z)}
d) Let A = {1,2,3,4} and B = {w,x,y,z}.
A function that is both one-to-one and onto is a function that contains the elements in A and all elements in B such that there are no repeats.
Example: {(1,w), (2,x), (3,y), (4,z)}
a) Both one-to-one and onto. b) Both one-to-one and onto. c) Both one-to-one and onto. d) Neither one-to-one nor onto, because not all of B's elements are considered (not onto) and elements in B are used more than once (not one-to-one). Range: y ≥ 0 e) Neither one-to-one nor onto, because not all of B's elements are considered (not onto) and elements in B are used more than once (not one-to-one). Range: y ≥ -1/4 f) Both one-to-one and onto.
a)
i) The question is really asking how many onto functions of f: A -> B are there if B = {v,w}. A nicer format of the formula for the number of onto functions is n!S(m,n).
Therefore, the number of functions f: A -> B if f(A) = {v,w} is 2!S(7,2).
ii) This question is similar to the previous one, since the range has the same cardinality. The only difference is that there are no specific elements in B being used, and so any two of the five choices can be selected to make onto functions from A to B.
Therefore, the number of functions f: A -> B if |f(A)| = 2 is C(5,2)2!S(7,2).
iii) 3!S(7,3)
iv) C(5,3)3!S(7,3)
v) 4!S(7,4)
vi) C(5,4)4!S(7,4)
b) In general, the number of functions f: A -> B if |f(A)| = k is C(|B|,k)k!S(|A|,k).
Class Example
How many ways can five houses be painted using three colours in such a way that each colour is used at least once?
The question is asking for the number of onto functions for the function f: {house₁,house₂,house₃,house₄,house₅} -> {colour₁,colour₂,colour₃}.
The first term represents the number of total functions with no conditions. The second term represents the number of functions that only use two colours. The third term represents the number of functions that only use one colour.
Therefore, there are 150 ways to paint the five houses with three colours such that each colour is used at least once.
Class Example
How many ways to partition the set {a,b,c,d} into three non-empty sets?
By definition, the number of ways is S(4,3).