# Finding number of functions in set A [duplicate]

Let $A = \{1, 2, 3, 4, \ldots, n\}$ (it follows that: $|A| = n$).

My objective is to count the number of functions: $f: A \rightarrow A$, that are monotonically increasing, i.e. $f(x) \leq f(x + 1)$, and the following equation holds: $f(x) = f(f(x+1))$.

It is trivial to see that any constant function of the form $f(x) = k; x, k \in A$ satisfies all conditions. There are exactly $n$ such functions, yet I want to disregard these and only count the non-constant functions.

However, I have not had any luck in finding a function that satisfies the second condition. Could anyone assist in finding such functions and the process of counting all functions that satisfy the conditions?

(Having studied some combinatorics, I know that the total number of functions (no conditions) from A to A, is $n^n$. Further, I may subtract the number of all constant functions, for which we established that it is equal to $n$. So far I have $n^n - n$. Since the function should be monotonically increasing, the number of all decreasing functions should be subtracted from the result, and furthermore, all monotonically increasing functions that do not satisfy the second condition should be subtracted. I suppose that there is a different approach though.)

-

## marked as duplicate by Brian M. Scott, Hagen von Eitzen, user17762, TMM, Peter TaylorMay 10 '13 at 16:15

With $a<b<n$, let $f(x)=\begin{cases}a&\text{if }x<n,\\b&\text{if }x=n\end{cases}$. – Hagen von Eitzen May 10 '13 at 15:27

Let $f(N) = k$ for some $k$. Then $f(f(N-1+1)) = f(f(N)) = f(k) = f(N-1)$.

Furthermore, $f(N-2) = f(f(N-1)) = f(f(k))$.

So we have:

$f(k) \leq k,\\ f(N-2) \leq f(f(k))$

Suppose $k = N-1$, then $f(N-1) = f(f(N)) = f(N-1)$, a tautology. Any number can be chosen to satisfy this equation so long as $f(N-1) \leq N-1$. Similarly, if $k=N-2$ then $f(N-2)=f(N-1) \leq k$

Working from $N=2,3,\dots$ I found:

$N = 2, |A| = 2 :\ (\{2,2\},\{1,1\})\\ N = 3, |A| = 4 :\ (\{3,3,3\},\{2,2,2\},\{1,1,2\},\{1,1,1\})\\ N = 4, |A| = 8 :\ (\{4,4,4,4\},\{3,3,3,3\},\{2,2,2,3\},\{1,1,2,3\},\{1,1,1,3\},\{2,2,2,2\},\{1,1,1,2\},\{1,1,1,1\})\\ N=5,|A|= 16 :\ (\{5,5,5,5,5\},\{4,4,4,4,4\},\{3,3,3,3,4\},\{2,2,2,3,4\},\{1,1,2,3,4\},\{1,1,2,2,4\},\{1,1,1,1,4\},\{3,3,3,3,3\},\{2,2,2,2,3\},\{1,1,2,2,3\},\{1,1,1,1,3\},\{2,2,2,2,3\},\{1,1,2,2,3\},\{2,2,2,2,2\},\{1,1,1,1,2\}\{1,1,1,1,1\})$

I haven't verified that the list for $N=5$ is exhaustive, nor worked out the induction yet, but it looks like it could be $2^{N-1}$

-