2
$\begingroup$

Consider all functions $f:\{1,2,3,4\} \rightarrow \{1,2,3,4\}$ which are one-one, onto and satisfy

if $f(k)$ is odd then $f(k+1)$ is even, $k = 1, 2, 3$

What is the total number of such functions?

The first thing that came to mind was to consider $f(k) = x^k$. (Clearly, if $f(k)$ is odd, $f(k+1)$ is even) This function is obviously, a particular case. Any conclusions made using this approach did not help. This answer given is 12. One of the approaches that I was suggested was to list all possible functions $f$ and then pick the ones which satisfied the condition. This was very easy to do in hindsight but is there some systematic way of doing this. Is there an approach other than brute-force?

$\endgroup$
4
  • $\begingroup$ @lulu Please do. $\endgroup$
    – mathx
    Jul 13, 2021 at 12:27
  • $\begingroup$ Note $l = (a,b,c,d)$ as the function $f$ with $f(i) =l_i$. Notice that $2$ and $4$ are interchangeable, the same that $1$ and $3$, so we can assume $1$ comes before $3$ and $2$ before $4$. Starting with $1$ we are forced to write $(1,2,3,4)$ or $(1,2,4,3)$. Starting with $2$ we are forced to $(2,1,4,3)$. Multiplying by $4$ (changing first pair and second pair) gives us the twelve solutions. $\endgroup$
    – AnilCh
    Jul 13, 2021 at 12:27
  • 1
    $\begingroup$ Editing done. If you click on "edit" you can see the syntax I used (same as that recommended by @SathvikAcharya). $\endgroup$
    – lulu
    Jul 13, 2021 at 12:28
  • $\begingroup$ @lulu Thank you lulu $\endgroup$
    – mathx
    Jul 13, 2021 at 12:30

2 Answers 2

4
$\begingroup$

Since $(\text{Even},\text{Even},\text{Odd},\text{Odd})$ and $(\text{Odd},\text{Odd},\text{Even},\text{Even})$ and $(\text{Even},\text{Odd},\text{Odd},\text{Even})$ each fail, there are three possibilities patterns on parity:

  • $(1,2,3,4) \to (\text{Odd},\text{Even},\text{Odd},\text{Even})$
  • $(1,2,3,4) \to (\text{Odd},\text{Even},\text{Even},\text{Odd})$
  • $(1,2,3,4) \to (\text{Even},\text{Odd},\text{Even},\text{Odd})$

and each of these has $2^2$ ways of distributing the odd and even values.

Extending to $\{1,2,3,\ldots,n\}$

  • if $n$ is odd then there is one parity pattern so $\left(\frac{n+1}{2}\right)! \left(\frac{n-1}{2}\right)!$ possibilities

  • if $n$ is even then there are $\frac n2+1$ parity patterns so $\left(\frac{n+2}{2}\right)! \left(\frac{n}{2}\right)!$ possibilities

This means that there are the same number of $(k+1)!k!$ possibilities for $n=2k$ and $n=2k+1$ starting numbers. Any pattern with $n$ odd corresponds to a shorter pattern with $n$ deleted from the pattern, and in reverse by inserting odd $n$ before a pattern with an even start, or after a pattern with an even end, or between two evens in a pattern which starts and ends odd.

$\endgroup$
4
  • $\begingroup$ Simple and concise. $\endgroup$
    – mathx
    Jul 13, 2021 at 12:33
  • $\begingroup$ Could you explain your edit? Why $\frac{n+1}{2}$! $\frac{n-1}{2}$! possibilities? $\endgroup$
    – mathx
    Jul 13, 2021 at 13:16
  • $\begingroup$ @mathx With $n$ odd, you must have a parity pattern of Odd, Even, Odd, Even, ..., Odd and then have $\frac{n+1}{2}$ odd numbers to order and $\frac{n-1}{2}$ even numbers to order. Try it with $n=3$ to get just $2$ possibilities $\endgroup$
    – Henry
    Jul 13, 2021 at 13:20
  • $\begingroup$ Henry, That is clear now. $\endgroup$
    – mathx
    Jul 13, 2021 at 13:28
1
$\begingroup$

If $f$ is a bijective function from $\{1,2,3,4\}$ to itself, then $f(1),f(2),f(3),f(4)$ are just $1,2,3,4$ in some order, so there is a one-to-one correspondence between such functions and orderings of $1,2,3,4$.

The restriction you have is that an odd number cannot be followed by another odd number, i.e. $1$ and $3$ are not consecutive in the ordering. The answer is the total number of orderings minus the number where $1,3$ are consecutive, both of which you should be able to calculate. (Hint for the second part: combine $1$ and $3$ to force them to be together, then double because they could be $1,3$ or $3,1$.)

$\endgroup$
2
  • 1
    $\begingroup$ And how could we attempt the general case, where domain is $\{1,2,3,...,n\}$? I see that no odd number should be immediately followed by another odd number. So, the stars and bars method? $\endgroup$ Jul 13, 2021 at 12:33
  • $\begingroup$ @Ritam_Dasgupta Yes, although it reduces to a fairly simple case of stars and bars. If $n$ is odd, the only way for this to happen is if all odd numbers are in odd positions, so $\frac{n+1}{2}!\frac{n-1}{2}!$. If $n$ is even you have odd numbers in the first $k$ odd positions and the last $n-k$ even positions (each corresponding to $\frac n2!\frac n2!$ ways), and there are $n+1$ possible choices of $k$. $\endgroup$ Jul 13, 2021 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .