We need to count functions f:S×S→S (where S={1,2,3,4}) that are onto, symmetric (f(a,b)=f(b,a)), and satisfy f(a,b)≥a for all (a,b)∈S×S.
Analyzing the constraint f(a,b)≥a, since f(a,b)=f(b,a), we also need f(a,b)≥b. Therefore:
f(a,b)≥max(a,b)
Next, because f(a,b)∈S={1,2,3,4} and f(a,b)≥max(a,b), we have f(4,b)≥4 for all b, so f(4,b)=4. Similarly, f(a,4)=4. This fixes all values involving 4.
Now consider values involving only {1,2,3}. For (a,b) with a,b∈{1,2,3}, we have f(a,b)≥max(a,b). Since f is symmetric, we only need to specify f(a,b) for a≤b.
f(3,3)≥3: choices are {3,4} (2 choices)
f(2,3)=f(3,2)≥3: choices are {3,4} (2 choices)
f(1,3)=f(3,1)≥3: choices are {3,4} (2 choices)
f(2,2)≥2: choices are {2,3,4} (3 choices)
f(1,2)=f(2,1)≥2: choices are {2,3,4} (3 choices)
f(1,1)≥1: choices are {1,2,3,4} (4 choices)
Without the onto constraint, the total number of assignments is 2×2×2×3×3×4=288.
The value 4 is already achieved from the forced values. We need the values 1, 2, and 3 to each appear at least once.
Value 1 can only appear at f(1,1), so f(1,1)=1 is forced. This reduces choices for f(1,1) to 1 option.
Value 2 can appear at f(1,2) or f(2,2), and it must appear in at least one of those entries.
Value 3 can appear at f(3,3), f(2,3), f(1,3), f(2,2), or f(1,2).
With f(1,1)=1, the remaining free choices are:
f(3,3): {3,4}, f(2,3): {3,4}, f(1,3): {3,4}, f(2,2): {2,3,4}, f(1,2): {2,3,4}.
Without the onto requirement for 2 and 3, there are 2×2×2×3×3=72 assignments.
To ensure both 2 and 3 appear, we use inclusion-exclusion. Let A be the set of assignments where 2 does not appear, and B the set where 3 does not appear.
In A, we must have f(1,2)∈{3,4} and f(2,2)∈{3,4}, giving ∣A∣=2×2×2×2×2=32.
In B, we must have f(3,3)=f(2,3)=f(1,3)=4 and f(2,2),f(1,2)∈{2,4}, giving ∣B∣=1×1×1×2×2=4.
In A∩B, both 2 and 3 are absent, so all five free values must be 4, giving ∣A∩B∣=1.
By inclusion-exclusion, the number of valid assignments is 72−32−4+1=37.
The answer is 37.