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 ?

  • $\begingroup$ 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$. $\endgroup$ May 28 at 10:07
  • $\begingroup$ 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.. ? $\endgroup$
    – Orion_Pax
    May 28 at 13:02
  • $\begingroup$ 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 $\endgroup$
    – Orion_Pax
    May 29 at 5:54

1 Answer 1


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$

  • $\begingroup$ 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. $\endgroup$ May 29 at 9:41

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.