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 !! :)


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$$

  • $\begingroup$ Thanks that is way more clear now! $\endgroup$ – FabolousPotato Mar 30 '18 at 21:48
  • $\begingroup$ You are welcome. I added an additional method of solution that may be closer to what you were attempting to do. $\endgroup$ – N. F. Taussig Mar 30 '18 at 21:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.