Calculate the number of functions $f:A \rightarrow B$ satisfying the condition $f(1) \le f(2)...\le f(n)$

Question

Let $n$ be a positive integer and Denote by $X$ the set of all functions $f$ from the set $A=\{1,2,...n\}$ to the set $B=\{1,2,3 \} $.

Calculate the number of functions $f:A \rightarrow B$ satisfying the condition $f(1) \le f(2)...\le f(n)$

This is an exam practice question for Discrete Math and I am trying to understand the solutions given. It is a relatively straight forward question, but the solutions aren't very clear.

It says that the list of values $(f(1),f(2),...,f(n))$ must have the form $(1,1,..,1,2,2,,,2,3,3,,,3)$. Let $k_i$ be the number of entries equal to $i$ in such a list for $i = 1,2,3$. The number of lists of this form is $k_1 + k_2 + k_3 = n$.

This is all fine, and then it says:

The number of such triples is ${n+2}\choose{2}$.

There is no further explanation. My first thought was that the solution would be the stirling number $S(n,3)$, but this clearly also counts functions which do not satisfy the condition. How was the solution of the number of triples derived?

Many thanks!

Answer 1

Define a function $f$ this way:

• Write the numbers $1,\ldots,n$.
• If there is some $j$ such that $f(j)=1$ and $f(j+1)>1$ put a line ($|$) between $j$ and $j+1$. If $f(1)\neq 1$ put the line at the beginning. If $f(n)=1$ put the line at the end.
• If there is some $j$ such that $f(j-1)<2$ and $f(j)=3$ then put a line between $j-1$ and $j$. If $f(n)\neq 3$, put it at the end. If $f(1)=3$, put it at the beginning.

This way you assign a function $f$ (of the set that you want to count) to a sequence of $n$ numbers and two lines, and this assignation is clearly bijective. Thus, you have to count how many of such sequences there are. Note that, although the numbers are different, you must write them in order, so the computation is the same as if they were indistiguishable. There are $n$ numbers and two lines, that is, $n+2$ symbols. Then the number of such functions is $\binom{n+2}2$, or, equivalently, $\binom{n+2}n$.

Answer 2

Suppose that the value $f(x)=1$ occurs $x_1$ times, $f(x)=2$ occurs $x_2$ times and $f(x)=3$ occurs $x_3$ times. Then we have $$x_1+x_2+x_3=n\ ,$$ where $x_1,x_2,x_3\ge0$, and the number of solutions for $(x_1,x_2,x_3)$ is $C(n+2,2)$.

Now we have to assign the $x_1$ copies of $1$ and the $x_2$ copies of $2$ and the $x_3$ copies of $3$ to $f(1),f(2),\ldots,f(n)$. But since $f(1)\le f(2)\le\cdots\le f(n)$ there is only one way to do this!

So the answer is $C(n+2,2)$.

Answer 3

There are $n+2$ places where the transition from $1$ to $2$ can take place -- before the first element (so $f(1) = 2$), at any of the $n$ elements, or after the last element (so $f(n) = 1$). One could take the point of view that there are fewer places for the shift from $2$ to $3$ to take place, but this is the hard way to do it.

There are two places where the image increments. Those two places can be anywhere from the $0^\text{th}$ position (so there are no $1$s) to the $n+1^\text{st}$ position (so there are no $3$s). Since swapping the locations of the two increments gives exactly the same function, you get ${n+2 \choose 2}$ such functions.