Question

Let S = {1, 2, 3, 4}.Then the number of elements in the set {f : S × S -> S : f is onto and f(a,b)=f(b,a) ≥ a ∀ (a, b)∈ S × S is _____.

Answer 1

The correct answer is 37
There are 16 ordered pairs in S × S. We write all these ordered pairs in 4 sets as follows.
A = {(1, 1)}
B = {(1, 4), (2, 4), (3, 4) (4, 4), (4, 3), (4, 2), (4, 1)}
C = {(1, 3), (2, 3), (3, 3), (3, 2), (3, 1)}
D = {(1, 2), (2, 2), (2, 1)}
All elements of set B have image 4 and only element of A has image 1.
All elements of set C have image 3 or 4 and all elements of set D have image 2 or 3 or 4.
We will solve this question in two cases.

Case I : When no element of set C has image 3.
Number of onto functions = 2 (when elements of set D have images 2 or 3)
Case II : When atleast one element of set C has image 3.
Number of onto functions = (23 – 1)(1 + 2 + 2) = 35
Therefore , total number of functions = 37