Consider the set of the functions $\mathrm{f:\{1,2,3,4,5\} \to \{1,2,3,4,5,6}\}$ that are non-increasing represented by the one-line notation $\mathrm{x_1x_2x_3x_4x_5}$; $\mathrm{\ (x_i=f(i)}$ for$\mathrm{\ i=1,\dots,5}$) ordered by lexicographic order. Determine the function appearing at the position $\mathrm{149}$.
Is there an efficient way to determine this function? I thought of counting the functions starting with $\mathrm{i=1,\dots,6}$, there are $\mathrm{{4+i-1}\choose{4}}$ functions for each $\mathrm{i=1,\dots,6}$. Then, I found that the function must start with $\mathrm{6}$ and after this, I repeated the same process but for the second position, having $\mathrm{{3+i-1}\choose{3}}$ with $\mathrm{i=1,\dots,6}$, now I conclude that the second position must be $\mathrm{4}$. One more time, I repeated the process and found that my function must start with $\mathrm{643}$,(...) and finally ended with the answer $\mathrm{64331}$.
You obtained the correct answer. The details are shown below.
The number of non-increasing functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ is completely determined by how many times each output appears in the range. For instance, if $1$ appears once, $3$ appears thrice, and $5$ appears once, then $f(1) = 5, f(2) = f(3) = f(4) = 3, f(5) = 1$.
Let $y_i$ be the number of times $i \in \{1, 2, 3, 4, 5, 6\}$ appears in the range of $f$. Then the number of non-increasing functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ is equal to the number of solutions of the equation $$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 5 \tag{1}$$ in the nonnegative integers.
A particular solution of equation $1$ in the nonnegative integers corresponds to the placement of $6 - 1 = 5$ addition signs in a row of five ones. For instance, $$1 + + 1 1 1 + + 1$$ corresponds to the solution $y_1 = 1, y_2 = 0, y_3 = 3, y_4 = 0, y_5 = 1$. The number of such solutions is the number of ways we can place $5$ addition signs in a row of five ones, which is $$\binom{5 + 6 - 1}{6 - 1} = \binom{10}{5} = 252$$ since we must select which five of the ten positions required for five ones and five addition signs will be filled with addition signs.
By similar reasoning, the number of non-increasing functions $f: \{1, 2, 3, \ldots, m\} \to \{1, 2, 3, \ldots, n\}$ is the number of solutions of the equation $$y_1 + y_2 + y_3 + \cdots + y_n = m$$ in the nonnegative integers, which is $$\binom{m + n - 1}{n - 1}$$ since we must choose which $n - 1$ of the $m + n - 1$ positions required for $m$ ones and $n - 1$ addition signs will be filled with addition signs.
How many functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ satisfy $f(1) = k$?
We still have four positions to fill. If $f(1) = k$, the only possible images for $f(2), f(3), f(4), f(5)$ are the positive integers less than or equal to $k$. Hence, if we let $y_i$ represent the number of times the digit $i \in \{1, 2, \ldots, k\}$ appears in the set $\{f(2), f(3), f(4), f(5)\}$, then $$y_1 + y_2 + \cdots + y_k = 4 \tag{2}$$ Equation $2$ is equation in the nonnegative integers with $$\binom{4 + k - 1}{k - 1}$$ solutions. Hence, $$ \begin{array}{c c} k & \text{number of functions satisfying $f(1) = k$}\\ \hline 1 & \dbinom{4 + 1 - 1}{1 - 1} = \dbinom{4}{0} = 1\\ 2 & \dbinom{4 + 2 - 1}{2 - 1} = \dbinom{5}{1} = 5\\ 3 & \dbinom{4 + 3 - 1}{3 - 1} = \dbinom{6}{2} = 15\\ 4 & \dbinom{4 + 4 - 1}{4 - 1} = \dbinom{7}{3} = 35\\ 5 & \dbinom{4 + 5 - 1}{5 - 1} = \dbinom{8}{4} = 70\\ 6 & \dbinom{4 + 6 - 1}{6 - 1} = \dbinom{9}{5} = 126 \end{array} $$ Since $1 + 5 + 15 + 35 + 70 = 126 < 149$, $f(1) = 6$.
How many functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ satisfy $f(1) = 6$ and $f(2) = k$?
If $f(1) = 6$ and $f(2) = k$, the only possible images for $f(3), f(4), f(5)$ are the positive integers less than or equal to $k$. Hence, if we let $y_i$ represent the number of times the digit $i \in \{1, 2, \ldots, k\}$ appears in the set $\{f(3), f(4), f(5)\}$, then $$y_1 + y_2 + \cdots + y_k = 3 \tag{3}$$ Equation $3$ is equation in the nonnegative integers with $$\binom{3 + k - 1}{k - 1}$$ solutions. Hence, $$ \begin{array}{c c} k & \text{number of functions satisfying $f(1) = 6$ and $f(2) = k$}\\ \hline 1 & \dbinom{3 + 1 - 1}{1 - 1} = \dbinom{3}{0} = 1\\ 2 & \dbinom{3 + 2 - 1}{2 - 1} = \dbinom{4}{1} = 4\\ 3 & \dbinom{3 + 3 - 1}{3 - 1} = \dbinom{5}{2} = 10\\ 4 & \dbinom{3 + 4 - 1}{4 - 1} = \dbinom{6}{3} = 20\\ 5 & \dbinom{3 + 5 - 1}{5 - 1} = \dbinom{7}{4} = 35\\ 6 & \dbinom{3 + 6 - 1}{6 - 1} = \dbinom{8}{5} = 70 \end{array} $$ Since $126 + 1 + 4 + 10 = 141 < 149 < 161 = 126 + 1 + 4 + 10 + 20$, $f(2) = 4$.
How many functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ satisfy $f(1) = 6$, $f(2) = 4$, and $f(3) = k$?
If $f(1) = 6$, $f(2) = 4$, and $f(3) = k$, the only possible images for $f(4)$ and $f(5)$ are the positive integers less than or equal to $k$. Since the sequence is non-increasing, $k \leq 4$. Hence, if we let $y_i$ represent the number of times the digit $i \in \{1, 2, \ldots, k\}$ appears in the set $\{f(4), f(5)\}$, then $$y_1 + y_2 + \cdots + y_k = 2 \tag{4}$$ Equation $4$ is equation in the nonnegative integers with $$\binom{2 + k - 1}{k - 1}$$ solutions. Hence, $$ \begin{array}{c c} k & \text{number of functions satisfying $f(1) = 6$, $f(2) = 4$, and $f(3) = k$}\\ \hline 1 & \dbinom{2 + 1 - 1}{1 - 1} = \dbinom{2}{0} = 1\\ 2 & \dbinom{2 + 2 - 1}{2 - 1} = \dbinom{3}{1} = 3\\ 3 & \dbinom{2 + 3 - 1}{3 - 1} = \dbinom{4}{2} = 6\\ 4 & \dbinom{2 + 4 - 1}{4 - 1} = \dbinom{5}{3} = 10 \end{array} $$ Since $141 + 1 + 3 = 145 < 149 < 151 = 141 + 1 + 3 + 6$, $f(3) = 3$.
How many functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ satisfy $f(1) = 6$, $f(2) = 4$, and $f(3) = k$?
If $f(1) = 6$, $f(2) = 4$, $f(3) = 3$, and $f(4) = k$, the only possible images for $f(5)$ are the positive integers less than or equal to $k$, so there are $k$ possible values for $f(5)$. Since the sequence is non-increasing, $k \leq 3$.
$$ \begin{array}{c c} k & \text{number of functions satisfying $f(1) = 6$, $f(2) = 4$, $f(3)= 3$, and $f(4) = k$}\\ \hline 1 & 1\\ 2 & 2\\ 3 & 3 \end{array} $$ Since $145 + 1 + 2 = 148 < 149 < 145 + 1 + 2 + 3 = 151$, $f(4) = 3$.
Moreover, the $149$th function is the first term in the sequence with $f(1) = 6$, $f(2) = 4$, $f(3) = 3$, and $f(4) = 3$. Hence, the $149$th non-increasing function $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6\}$ when the functions are written in lexicographic order is the function defined by $f(1) = 6, f(2) = 4, f(3) = 3, f(4) = 3, f(5) = 1$, which agrees with your answer.