# Number of functions mapping consecutive numbers to consecutive letters .

Let $$N=\{1,2, \ldots, 9\}$$ and $$L=\{a, b, c\}$$ which if the following is correct ?

• $$L \cup N$$ is arranged on a line with the letters appearing consecutively (in any order). The number of such arrangements are less than $$10 ! \times 5$$.
• More than half of the functions from $$N$$ to $$L$$ have $$b$$ in their range.
• The number of one-to-one functions from $$L$$ to $$N$$ is less than 512 .
• The number of functions $$N$$ to $$L$$ that do not map consecutive numbers to consecutive letters is greater than $$512 .$$

i have checked the first three parts as such for first one its false since it should be haviing 3! = 6 instead of 5 there for total permutations of L elements . Next one is simply $$3^9 - 2^9$$ by complementary couting . Third one is the $$\binom{9}{3} 3!$$ (less than 512) , next the final option i am not getting the statement at all , i think(for complementary counting) it means we must have all terms having consecutive letters as output but there are only 3 letters so how can it be possible ? Or is that means answer is same as total number of functions itself ?

• A compliment is an expression of praise. The complement of a set $A$ in the universe $U$ is the set $U \setminus A$ consisting of elements in the universe that are not in $A$. You meant complementary. The way I read the last question is that if $f(k) = a$, then $f(k + 1) \neq b$ and that if $f(k) = b$, then $f(k + 1) \neq c$. May 28 at 10:07
• I see indeed i rectified and yeah now makes sense , but how will we solve for all possible type of that one ? I would do like case by case of having either 1 to be a etc.. ? May 28 at 13:02
• I think i got a method for getting a lower bound on it , please for once check my solution here @N.F.Taussig which i am sharing here soon May 29 at 5:54

Let $$W_n$$ denotes the number of functions having first $$'n'$$ natural numbers as domain and co domain as $${a,b,c}$$ having first element mapping to $$a$$ , similarily $$Z_n$$ denotes mapping in which first element is map to $$b$$ . And $$Q_n$$ denotes functions in which the first element mapping is with $$c$$ , then as we know that if anywhere the element mapping is a then next element mapping will either be $$a$$ or $$c$$ but not $$b$$ , similarily for other two $$b$$ and $$c$$ ones we get the recurrence relations of
$$Z_n = Z_{n-1} + W_{n-1}$$ ,$$Q_n = Q_{n-1} + Z_{n-1} + W_{n-1}$$ and $$W_n = Q_{n-1} + W_{n-1}$$ .
Total functions $$\phi(n)$$ for a specific $$n$$ would be of form = $$2\phi(n-1) + W_{n-1}$$ , as can observe the $$W_{n-1}$$ cannot be negative therefore lower bound is $$2\phi(n-1)$$ , as $$\phi(1) = 3$$ , therefore $$\phi(9)$$ is atleast $$3×2^8$$ which is already greater than $$2^9$$ since $$3>2$$
• You should explain why the answer is at least $3 \cdot 2^8$. In particular, you should explain that a $c$ can be followed by any of the three letters. May 29 at 9:41