How many injective functions $f: A \to B$ satisfy $f(a_1) = b_1$ or $f(a_2)=b_2$?

465 Views Asked by At

I've been stuck on this question for hours, and am having trouble trying to start this question. If anyone could help, that would much appreciated.

The question is Let $A = \{a_1, a_2, a_3, a_4\}$ and $B = \{b_1, b_2, b_3, b_4, b_5\}$ (where $|A| =4$ and $|B|=5$), how many injective functions $f: A \to B$ satisfy $f(a_1) = b_1$ or $f(a_2)=b_2$?

2

There are 2 best solutions below

0
On

Define $F_1 = \{f\colon A\to B | f(a_1) = a_1, f \text{ injective} \}$. Define $F_2$ similarly for $f(a_2) = b_2$. Then use the fact that functions in $F_1$ are injective to find the cardinality of $F_1$ and similarly for $F_2$. Once you've done this, find the cardinality of $F_1 \cap F_2$. Then the total number of injective functions $f\colon A\to B$ satisfying $f(a_1) = b_1$ or $f(a_2) = b_2$ is $|F_1| + |F_2| - |F_1 \cap F_2|$ by the inclusion exclusion principle.

2
On

Case 1: $a_1$ is mapped to $b_1$

There are four ways to map $a_2$; to $b_2, b_3, b_4,$ of $b_5$.

There are three ways to map $a_3$. (To any of the three remaining values).

There are two ways to map $a_4$. (To any of the two remaining.)

That's 24 ways.

Case 2: $a_1$ is not mapped to $b_1$

Then $a_2$ must map to $b_2$.

There are three ways to map $a_1$; to $b_3, b_4, b_5$

After $a_1$ and $a_2$ are mapped; there are three remaining ways to map $a_3$.

After $a_1, a_2,$ and $a_3$ are mapped there are two remaining ways to map $a_4$.

That's $18$ ways.

That's $24 + 18 = 42$ ways. I'm going to need a lot more pinkies.