Question

Let $S=\{1,2,3,4\}$. Then the number of elements in the set $\{ f : S \times S \rightarrow S : f$ is onto and $f ( a , b )= f ( b , a )$ $\geq a \forall( a , b ) \in S \times S \}$ is

Answer 1

$(1,1),(1,4),(4,1),(2,4),(4,2),(3,4),(4,3)$,
$(4,4)-$ all have one choice for image.
$(2,1),(1,2),(2,2)-$ all have three choices for image
$(3,2),(2,3),(3,1),(1,3),(3,3)-$ all have two choices for image.
So the total functions $=3 \times 3 \times 2 \times 2 \times 2=72$
Case 1: None of the pre-images have 3 as image
Total functions $=2 \times 2 \times 1 \times 1 \times 1=4$
Case 2 : None of the pre-images have 2 as image
Total functions $=2 \times 2 \times 2 \times 2 \times 2=32$
Case 3 : None of the pre-images have either $ 3$ or $2$
as image
Total functions $=1 \times 1 \times 1 \times 1 \times 1=1$
$\therefore$ Total onto functions $=72-4-32+1=37$