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

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!

• This is the classic pirates-and-gold formula (well at least that's how I learned it). I would be very surprised if you did not learn it in your discrete math course. You should look back over your notes on counting and see if you can figure it out. Commented Jun 19, 2014 at 6:57
• Look at Wikipedia, article on Stars and Bars. (One can do the counting without the machinery, since $3$ is very small.) we are counting the number of ways to divide $n$ identical candies between $3$ kids, or the number of solutions of $x_1+x_2+x_3=n$ in non-negative integers. Commented Jun 19, 2014 at 6:57

## 3 Answers

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$.

• ahh, yes yes. Once I started drawing the lines, it becomes really clear. Thanks a lot, I knew it was simple, but my mind was just drawing a blank.
– JJJ
Commented Jun 19, 2014 at 7:26

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)$.

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.