Mathematics

Mathematics

Problem

Let A={a1,a2,a3,a4}A=\{a_1,a_2,a_3,a_4\} and B={b1,b2,b3,b4}B=\{b_1,b_2,b_3,b_4\}. How many bijective functions f: ⁣:A→Bf:\colon A\to B satisfy the condition f(a1)≠b1f(a_1)\neq b_1?
Intuitive explanation

This is a derangement-adjacent counting problem where you need bijections with a forbidden assignment. The key insight is to use complementary counting: find all bijections from AA to BB, then subtract those where f(a1)=b1f(a_1) = b_1. When f(a1)=b1f(a_1) = b_1, the remaining three elements must form a bijection between the remaining sets—a simpler subproblem. This transforms a constraint into a straightforward subtraction.

Intuitive explanation

This is a derangement-adjacent counting problem where you need bijections with a forbidden assignment. The key insight is to use complementary counting: find all bijections from AA to BB, then subtract those where f(a1)=b1f(a_1) = b_1. When f(a1)=b1f(a_1) = b_1, the remaining three elements must form a bijection between the remaining sets—a simpler subproblem. This transforms a constraint into a straightforward subtraction.

Browse the problem library