How many functions are possible to create in this example?

Question

Let $A = \{ 1,2,3,4 \}$ Let $F$ be a set of all functions from $A \to A$.

Let $S$ be a relation defined by : $\forall f,g \in F$ $fSg \iff f(i) = g(i)$ for some $i \in A$

Let $h: A \to A$ be the function $h(x) = 1 $ for all $x \in A$.

How many functions $g \in F$ are there so that $gSh$ ?

My solution : $gSh$ means that $g(i) = h(i)$ for some $i \in A$. So $g(i) = 1$.

So number 1 always needs to connect to some x - 4 choices.

Then we have $3$ left-over numbers that can connect to $4$ numbers each.

So solution is $4 \cdot 4 \cdot 4 \cdot 4$. Is this correct at all? Thanks in advance !! :)

Answer 1

Method 1: We subtract the number of functions that do not satisfy the given condition from the total.

If we did not have the restriction that $g(i) = 1$ for some $i \in A$, there would be four choices in the codomain for each of the four elements in the domain. Hence, in total, there are $4^4$ functions $f: A \to A$.

From these, we subtract those functions that do not satisfy the condition $g(i) = 1$ for some $i \in A$.

Let $f$ be such a function. Then $f(i) \neq 1$ for each $i \in A$. Thus, $f(i)$ must assume one of the three values $2$, $3$, or $4$. Hence, there are $3$ ways to assign $f(i)$ for each of the four elements in $A$. Thus, there are $3^4$ such functions.

The number of functions $g: A \to A$ that satisfy $g(i) = 1$ for some $i \in A$ is therefore $4^4 - 3^4$.

Method 2: We count directly.

Suppose that exactly $k$ elements in $A$ map to $1$. There are $\binom{4}{k}$ ways to select $k$ elements in $A$ that map to $1$ and $3$ possible outcomes for each of the remaining $4 - k$ elements in $A$. Thus, the number of functions $g: A \to A$ that satisfy $g(i) = 1$ for some $i \in A$ is $$\binom{4}{1}3^3 + \binom{4}{2}3^2 + \binom{4}{3}3^1 + \binom{4}{4}3^0$$

Answer 2

I agree with N.F. Taussig's answer. This response isn't an answer, but a warning about the following faulty reasoning:

I can choose any element $i$ from {1,2,3,4} so that $g(i)=1.$ Suppose I set $i=1.$ This leaves $g(2), g(3),$ and $g(4)$ totally unrestricted. Therefore, there are $4^3$ functions $g$ such that $g(1)=1 \Rightarrow gSh.$

Since I have 4 choices for the original $i$, there must be $4\times 4^3$ satisfying functions $g.$

First of all, $4\times 4^3 = 4^4$ can't be right, because (as N.F. Taussig indicated) there are only $4^4$ functions to begin with, and they can't all be satisfying functions.

It is true that there are exactly $4^3$ satisfying functions when (for example) $i$ is set to 1, and also $4^3$ satisfying functions when $i$ is set to 2 (i.e. where $g(2)$ is required to be 1). However, these two separate sets of $4^3$ functions are not mutually exclusive; a function can have both $g(1)=1$ and $g(2)=1.$

The whole point of N.F. Taussig's Method 1 approach is to avoid the complexity of having to enumerate all of the intersections in the 4 separate sets of functions, where each set has $4^3$ members.