Q10 of 107 Page 29

Find the number of all onto functions from the set {1, 2, 3, ..., n} to itself.

Onto function from the set {1, 2, 3, ..., n} to itself is simply a permutation on n symbols 1, 2, 3, …, n.

Therefore, the total number of onto maps from {1, 2, 3, …, n} to itself is the same as the total number of permutations on n symbols 1, 2, 3, …, n, which is n!


More from this chapter

All 107 →
8

Given a non-empty set X, consider P(X) which is the set of all subsets of X.

Define the relation R in P(X) as follows:


For subsets A, B in P(X), ARB if and only if A ⊂ B. Is R an equivalence relation on P(X)? Justify your answer.

 9

Given a non-empty set X, consider the binary operation ∗: P(X) × P(X) → P(X) given by A ∗ B = A ∩ B ∀ A, B in P(X), where P(X) is the power set of X. Show that X is the identity element for this operation and X is the only invertible element in P(X) with respect to the operation ∗.

 11

Let S = {a, b, c} and T = {1, 2, 3}. Find F–1 of the following functions F from S to T, if it exists.

F = {(a, 3), (b, 2), (c, 1)}

 11

Let S = {a, b, c} and T = {1, 2, 3}. Find F–1 of the following functions F from S to T, if it exists.

F = {(a, 2), (b, 1), (c, 1)}