Hey there, let's break down why your second approach gave an overcount, and walk through the correct way to calculate this.

First, let's recap the problem: we need onto (surjective) functions where f(1)=x is fixed. Since B has 3 elements and A has 4, exactly one element in B will be mapped to by two elements of A, and the other two will each have exactly one preimage. That's a key observation to avoid overcounting.

Why your 18-count approach is wrong #

Your second method counts some functions multiple times. Let's take an example: the function where f(1)=x, f(2)=y, f(3)=y, f(4)=z. This function gets counted twice in your calculation:

• Once when you pick element 2 as the "fourth" element (mapping it to y, with f(3)=z, f(4)=y? Wait no, actually in your reasoning, when you pick element 2 as the fourth, you set f(3)=z, f(4)=y, then map 2 to y. Then when you pick element 3 as the fourth, you set f(2)=y, f(4)=z, then map 3 to y. Same function, counted twice.

Every function where the duplicate mapping is to y or z gets counted multiple times (once for each element that maps to the duplicated value), which inflates your total to 18 instead of the correct 12.

Correct way to count (case analysis) #

Let's split into cases based on which element in B has the duplicate preimage:

1. Case 1: Duplicate mapping to x

   • We already have f(1)=x. We need exactly one more element from {2,3,4} to map to x, and the other two must map to y and z (one each).
   • Choose which element maps to x: 3 choices (2, 3, or 4).
   • The remaining two elements can be mapped to y and z in 2! = 2 ways.
   • Total for this case: 3 * 2 = 6 functions.

2. Case 2: Duplicate mapping to y

   • We need two elements from {2,3,4} to map to y, and the third to map to z (to ensure z is covered).
   • Choose which two elements map to y: C(3,2) = 3 choices (groups like {2,3}, {2,4}, {3,4}).
   • The remaining element maps to z (only 1 way).
   • Total for this case: 3 functions.

3. Case 3: Duplicate mapping to z

   • This is symmetric to Case 2: two elements from {2,3,4} map to z, the third maps to y.
   • Total for this case: 3 functions.

Adding all cases together: 6 + 3 + 3 = 12, which matches your initial manual count.

Another way: Inclusion-Exclusion Principle #

We can also calculate this using inclusion-exclusion to confirm:

• Total functions where f(1)=x: 3^3 = 27 (each of 2,3,4 has 3 choices).
• Subtract functions that don't cover y (all 2,3,4 map to x or z): 2^3 =8.
• Subtract functions that don't cover z (all 2,3,4 map to x or y): 2^3=8.
• Add back functions that cover neither y nor z (all map to x): 1 (we subtracted this twice, so add once).
• Final count: 27 -8 -8 +1 =12.

This confirms your initial manual count was correct, and the overcount in the second approach came from double-counting functions where y or z had duplicate preimages.

备注：内容来源于stack exchange，提问作者aarbee