Number of functions $f : \{1, 2, ..., n\} → \{1, 2, ..., n + 2\}$ satisfying $f (x) < f (y)$

Question

Let n be a positive integer. What is the number of functions $f : \{1, 2, ..., n\} → \{1, 2, ..., n + 2\}$ satisfying $f (x) < f (y)$ for every $x, y ∈ \{1, 2, ..., n\}$ such that $x < y$?

I've had similar examples in the past but I can't figure out the general procedure. I know that $|A| = n$ and $|B| = m$ then we have $n^m$ elements. But I can't tie it together. I would greatly appreciate your help.

Answer 1

As the inequality is strict, we then have firstly that $f$ is in injective.

Now, when we map the numbers $\{ 1, \ldots n \}$ to $\{ 1, \ldots, n+2 \}$ we have to skip exactly $2$ numbers somewhere to preserve the order. We can choose which numbers these are from the $n+2$ in ${n+2}\choose{2}$ ways

Answer 2

HINT:

Once you know the image of $f$, the function $f$ is uniquely determined. Now, in how many ways can you choose the image of $f$? ( it will be a subset with $n$ elements)

Answer 3

Hint: if you delete any two elements in $\{1,2,....,n+2\}$ you get the function you want. So...