Find the number of surjective (onto) functions $f$ from $\{1,2,3,\ldots,20\}$ to $\{1,2,3,\ldots,20\}$ such that $f(k)$ is a multiple of 3 whenever $k$ is a multiple of 4.
Multiples of 4 in $\{1,\ldots,20\}$: $\{4,8,12,16,20\}$ — 5 elements. Their images must be multiples of 3 in $\{1,\ldots,20\}$: $\{3,6,9,12,15,18\}$ — 6 elements.
Assign the 5 multiples-of-4 to 5 of the 6 multiples-of-3 (injectively, since $f$ is onto): $6 \times 5 \times 4 \times 3 \times 2 = 6!/(6-5)! = 720$... but we need surjection on all 20 elements.
The remaining 15 domain elements map to the remaining 15 codomain elements (after fixing the 5 images above): $(15)!$ ways. But 1 multiple-of-3 is unused by the multiples-of-4, so it must be covered by remaining 15 elements.
Total $= 6! \times (15)! = (15)! \times 6!$
Sign in to join the conversation and share your thoughts.
Log In to Comment