Number of Functions

Class Notes & Tough Questions

Basic Function Counts: f : A → B

Let n( A) = m and n( B) = n.

• Total Functions = nm

• One-One (Injective) = n Cm · m! (if n ≥ m, else 0)

• Many-One = Total − One-One

• Onto (Surjective) Formula (for m ≥ n):

nm − {n C1 (n − 1)m − n C2 (n − 2)m + n C3 (n − 3)m − . . . }

• Into Functions = Total − Onto

Standard Cases
Case 1: n( A) = 4, n( B) = 4

• One-One → 4! = 24

• Many-One → 44 − 4!

• Onto → 4! = 24

• Into → 44 − 4!

Case 2: n( A) = 5, n( B) = 3

• One-One → 0

• Onto → 35 − 3 C1 · 25 − 3 C2 · 15 = 243 − [3(32) − 3(1)] = 243 − 93 = 150

 

Alternative
 (Group Distribution
 Method):
5! 5!
+ × 3! = (10 + 15) × 6 = 150
3!1!1!2! 2!2!1!2!

• Many-One → 35 = 243

• Into → Total − Onto = 243 − 150 = 93

Case 3: n( A) = 3, n( B) = 5

• One-One → 5 C3 · 3! = 60

• Many-One → 53 − 60 = 65

• Onto → 0

• Into → 53 = 125

1
Strictly Increasing / Decreasing Functions
Let n( A) = 10 and n( B) = 50.

1. No. of strictly increasing functions = 50 C10

2. No. of strictly decreasing functions = 50 C10

3. No. of strictly monotonic functions = 2 × 50 C10

4. No. of increasing functions (non-strict) = 50+10−1 C10 = 59 C10

5. No. of decreasing functions (non-strict) = 59 C10

2
 Tough Questions & Solutions

Question 1

No. of functions f : {1, 2, 3, . . . , 20} → {1, 2, 3, . . . , 20} that are onto, such that f (k) is a multiple
of 3 whenever k is a multiple of 4.

Solution:
Multiples of 4 in Domain (A1 ) = {4, 8, 12, 16, 20} ⇒ n( A1 ) = 5
Multiples of 3 in Codomain (B1 ) = {3, 6, 9, 12, 15, 18} ⇒ n( B1 ) = 6
Since n( A1 ) = 5 < n( B1 ) = 6, mapping 5 elements onto 6 elements is impossible.
Hence, number of such onto mappings = 0.
(Note: The general formula for onto mapping elements evaluates to 65 − {6 · 55 − 15 · 45 . . . } = 0)

Question 2

Let A = { a, b, c} and B = {1, 2, 3, 4}. Then find the number of elements in the set:

C = { f : A → B | 2 ∈ f ( A) and f is not one-one}

Solution:
Case 1: f ( A) = {2}.
All 3 elements map to 2. Number of ways = 1.
Case 2: f ( A) = {2, x } where x ∈ {1, 3, 4}.
Choose x: 3 C1 = 3 ways.
Number of ways to map 3 elements onto 2 elements = 23 − 2 = 6.
Ways for Case 2 = 3 × 6 = 18.
Total Elements in C = 1 + 18 = 19.

Question 3

Let A = {1, 2, 3, . . . , 7}. Then find the no. of bijective functions f : A → A such that f (1) +
f (2) + f (3) = 12.

Solution:
Possible subsets of 3 distinct elements from A summing to 12:
(1, 4, 7), (1, 5, 6), (2, 3, 7), (2, 4, 6), (3, 4, 5).
Total = 5 such subsets.
Ways to assign these to f (1), f (2), f (3) = 3! ways.
Ways to map the remaining 4 elements to the remaining 4 outputs = 4! ways.
Total Bijective Functions = 5 × 3! × 4! = 5 × 6 × 24 = 720.

Question 4

Let X = { a, b, c, d, e} and Y = {b1 , b2 , b3 }. Find the no. of functions f : X → Y such that it is

onto and there are exactly three elements in X such that f ( x ) = b1 .

3
Solution:
Ways to choose 3 elements from X to map to b1 : 5 C3 .
The remaining 2 elements must map to b2 , b3 such that both are covered (onto).
Ways to map 2 distinct elements onto 2 distinct outputs = 2!.
Total Functions = 5 C3 × 1 × 2! = 10 × 2 = 20.

Question 5

The no. of bijections from {1, 3, 5, . . . , 99} → {2, 4, 6, . . . , 100} such that f (3) > f (9) > f (15) >
· · · > f (99) is:

Solution:
Total elements in domain = 50. Total elements in codomain = 50.
The sequence 3, 9, 15, . . . , 99 forms an A.P. with a = 3, d = 6.
99 = 3 + (n − 1)6 ⇒ 6(n − 1) = 96 ⇒ n = 17.
There are 17 specific elements with a strict decreasing condition.
Ways to choose 17 images for these from the 50 available: 50 C17 .
(They will automatically arrange in decreasing order in exactly 1 way).
The remaining 50 − 17 = 33 elements can map to the remaining 33 elements in 33! ways.
Total Bijections = 50 C17 · 33!.

Question 6

Let A = {1, 3, 5, 7} and B = {2, 4, 6, 8}. Let f : A → B. Find the no. of functions such that:

(i) f (i ) ≥ i
f (1) ∈ {2, 4, 6, 8} → 4 choices
f (3) ∈ {4, 6, 8} → 3 choices
f (5) ∈ {6, 8} → 2 choices
f (7) ∈ {8} → 1 choice
Total = 4 × 3 × 2 × 1 = 4! = 24.
(ii) f (i ) − i > 2 ⇒ f (i ) > i + 2
f (1) > 3 → {4, 6, 8} (3 choices)
f (3) > 5 → {6, 8} (2 choices)
f (5) > 7 → {8} (1 choice)
f (7) > 9 → (0 choices)
Total = 0.
(iii) f (i ) ≥ 6 ∀i ∈ {1, 3, 5, 7}
Every element has exactly 2 choices ({6, 8}).
Total = 2 × 2 × 2 × 2 = 16.
(iv) f (i ) ̸= i + 1
f (1) ̸= 2, f (3) ̸= 4, f (5) ̸= 6, f (7) ̸= 8.
Every element has exactly 3 choices.
Total = 3 × 3 × 3 × 3 = 81.

4
Question 7

If A = {1, 2, 3, 4} and f : A → A. Total no. of invertible functions f such that f (2) ̸= 2, f (4) ̸=
4 and f (1) = 1 is:

Solution:
Since f (1) = 1, we must map {2, 3, 4} → {2, 3, 4} bijectively.
Total unconstrained bijections for these 3 elements = 3! = 6.
Let n( X ) be the set of bijections where f (2) = 2 ⇒ 2! = 2.
Let n(Y ) be the set of bijections where f (4) = 4 ⇒ 2! = 2.
n( X ∩ Y ) is where f (2) = 2 and f (4) = 4 ⇒ 1! = 1.
Unwanted cases (where f (2) = 2 OR f (4) = 4) = n( X ∪ Y ) = 2 + 2 − 1 = 3.
Required functions = Total - Unwanted = 6 − 3 = 3.

Question 8

Given A = {1, 2, 3, 4} and B = {1, 2, 3, . . . , 7}. No. of functions that are one-one satisfying
f (i ) ̸= i ∀i.

Solution (Using Complement/Derangement Method):

Total one-one functions = 7 P4 = 7 × 6 × 5 × 4 = 840.
Let Ai be the set of one-one functions where f (i ) = i.
n ( A1 ∪ A2 ∪ A3 ∪ A4 ) = ∑ n ( A i ) − ∑ n ( A i ∩ A j ) + ∑ n ( A i ∩ A j ∩ A k ) − n ( A1 ∩ A2 ∩ A3 ∩ A4 )
= 4 C1 · 6 P3 − 4 C2 · 5 P2 + 4 C3 · 4 P1 − 4 C4 · 3 P0
= 4(120) − 6(20) + 4(4) − 1(1)
= 480 − 120 + 16 − 1 = 375.
Total valid functions = Total - Complement = 840 − 375 = 465.

Question 9

Let A = {1, 2, 3, 4, 5, 6, 7}. No. of surjective functions from A → A such that f (i ) = i for at
least four elements is:

Solution:
Since n( A) = n( B), surjective ≡ bijective.
At least 4 fixed elements = (Exactly 4) + (Exactly 5) + (Exactly 6) + (Exactly 7) fixed.
Formula: ∑ n Cr · Dn−r where Dk is the derangement of k elements.
= 7 C4 · D3 + 7 C5 · D2 + 7 C6 · D1 + 7 C7 · D0
(Derangements: D3 = 2, D2 = 1, D1 = 0, D0 = 1)
= 35(2) + 21(1) + 7(0) + 1(1)
= 70 + 21 + 0 + 1 = 92.

Question 10

Given A = {1, 2, 3, 4, 5}, then no. of functions f : A → A satisfying f ( f (n)) = n ∀n ∈ A.

Solution:
f ( f (n)) = n implies the function is its own inverse (involution). It can only contain 1-cycles
and 2-cycles.
Cases for 5 elements:

5
1. All 1-cycles (identity map): 1 way.
2. Three 1-cycles, One 2-cycle: 5 C2 · 1 = 10 ways.
5C · 4C
4 2
3. One 1-cycle, Two 2-cycles: · 1 = 5 × 3 = 15 ways. (or simply 5 C4 × 3)
2!
Total = 1 + 10 + 15 = 26.

Question 11

Let S = {1, 2, 3, . . . , 7}. The no. of functions f : S → S such that f (m · n) = f (m) · f (n) for
m, n ∈ S and m · n ∈ S.

Solution:
Put m = 1, n = 1 ⇒ f (1) = [ f (1)]2 ⇒ f (1) = 1 (since 1 ∈ S).
For elements 5 and 7: They do not form valid products ≤ 7 other than with 1.
So f (5 · 1) = f (5) ⇒ f (5) can be any of the 7 values.
Similarly, f (7) can be any of the 7 values.
For the set {2, 3, 4, 6}:
Case 1: Let f (2) = 1 ⇒ f (4) = f (2)2 = 1.
Then f (6) = f (2 · 3) = 1 · f (3) = f (3).
Here, f (3) can take any value from {1 . . . 7} (7 choices).
Case 2: Let f (2) = 2 ⇒ f (4) = 22 = 4.
Then f (6) = 2 · f (3). Since f (6) ≤ 7, f (3) ∈ {1, 2, 3} (3 choices).
(Note f (2) cannot be ≥ 3 since f (4) = f (2)2 ≤ 7).
Total ways for {2, 3, 4, 6} = 7 + 3 = 10.
Total Functions = 1 (for 1) × 7 (for 5) × 7 (for 7) × 10 (for the rest) = 490.