Counting the number of functions

Question

Let $A$ and $B$ be subsets of the set $\Bbb Z$ for all integers, and let $\mathscr F$ denote the set of all functions $f:A\rightarrow B.$ Assume $A = \{1,2,3\}$ and $B=\{1,2,...,n\}$ where $n\ge 2$ is a fixed integer.

Define a relation $R$ on $\mathscr F$ by : for any $f,g \in \mathscr F$, $\;fRg\;$ if and only if $f - g$ is a constant function (i.e. there is a constant $c$ so that $f(x) - g(x) =c$ for all $x\in A$).

(b) Find the number of functions $f \in \mathscr F$ so that $[f]= \{f\}$

So this means I need to find the number of functions so that $1$ and $n$ are in the range. So for example $f = \{(1,n),(2,1),(3,n-2$ choices$)\}$, so I have 1 choice for the first 2 and n-2 choices for the third. So $1 \times 1 \times (n-2) = n$ functions. But I have to consider the permutations too so it would be $3! \times n$ But this would be true if the functions were one-to-one. What if they are not?

(c) Find the number of distinct equivalence classes $[f]$ of $R$.

For this one I need to find the number of functions so that $1$ is in the range right? so functions that have $f(x)=1$. For example $f = \{(1,1),(2,n$ choices$),(n$ choices$)\}$ and taking the permutations into consideration it would be $3! \times n^2$?

Answer 1

(b) It’s probably simplest to subtract the functions that you don’t want from the $3^n$ functions in $\mathscr{F}$. There are $(n-2)^3$ functions from $A$ to $B$ whose ranges contain neither $1$ nor $n$. There are $(n-1)^3$ whose ranges do not contain $1$, so there are $(n-1)^3-(n-2)^3$ whose ranges contain $n$ but not $1$. Similarly, there are $(n-1)^3-(n-2)^3$ whose ranges contain $1$ but not $n$. That’s a total of

$$(n-2)^3+2\left((n-1)^3-(n-2)^3\right)=2\cdot(n-1)^3-(n-2)^3=n^3-6n+6$$

functions whose ranges are missing at least one of the numbers $1$ and $n$, so there are $$n^3-\left(n^3-6n+6\right)=6n-6=6(n-1)$$ functions $f\in\mathscr{F}$ such that $[f]=\{f\}$.

(c) Yes, every equivalence class contains exactly one function whose range contains $1$. Here it’s definitely easiest to count the functions whose ranges don’t contain $1$, and I already did that in answering (b).

Answer 2

b) If the functions were one-to-one then f={(1,n),(2,1),(3,[n-2, not 1 or n, choices]) so 3! x (n-2)

By allowing the third element in the domain to be 1, n, or anything else, you are not restricting your count to one-to-one functions. Eg. f={(1,n),(2,1),(3,n)} is not one-to-one.

I think that 3! x n would count some functions more than once though.

Is this for Sands' class by chance? Awesome coincidence otherwise.