How many functions f from {1,2,3,4,5,6,7,8} onto {1,2,3,4} (i.e.…

Question

How many functions f from {1,2,3,4,5,6,7,8} onto {1,2,3,4} (i.e. surjective functions, every value 1,2,3,4 is hit at least once) satisfy both f(1) is not equal to 1 and f(2) is not equal to 2?

Accepted Answer

Let U be the set of all functions f:{1..8}->{1..4} with f(1)!=1 and f(2)!=2. For position 1 there are 3 choices, position 2 there are 3 choices, positions 3..8 there are 4 choices each: |U| = 3*3*4^6 = 9*4096 = 36864.

We need those that are surjective. Apply inclusion-exclusion on the set of missed values. For a subset T of {1,2,3,4} of forbidden (missed) target values, count functions in U whose image avoids T, then alternate signs.

For a chosen T, each position is restricted to the allowed values not in T, but positions 1 and 2 also drop their own banned value (1 and 2 respectively, when those are still allowed). Let a = number of allowed values for position 1 = |{1..4}\T| minus (1 if 1 not in T), b = same for position 2 with value 2, and c = 4-|T| allowed values for positions 3..8. Count = a*b*c^6.

Computing N(T) for every T and forming sum over T of (-1)^{|T|} N(T) gives the surjections. Carrying out the 16-term alternating sum yields 23114. (The direct enumeration confirms it.)

Final answer: 23114

How many functions f from {1,2,3,4,5,6,7,8} onto {1,2,3,4} (i.e.…

Stuck on a problem like this?