Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
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

1 Answer 1

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

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.