Any non-decreasing map [tex]f[/tex] partitions [tex]1,\ldots,n[/tex] into continuous blocks, where every member in a block maps to the same value. For example if [tex]f[/tex] maps [tex]1,2,3,4,5[/tex] to [tex]2,2,2,3,4[/tex] repectively then there are [tex]3[/tex] blocks [tex]\{1,2,3\}, \{4\},[/tex] and [tex]\{5\}[/tex].
Every block other than the first must be of length 1. To see why suppose the previous block is [tex]\{x,\ldots,y\}[/tex], from our conditions we know [tex]f(y)=f(f(y+1))[/tex], and if the block is of length 2 or greater we must have [tex]f(y+2)=f(y+1)[/tex] but this means [tex]f(y+1)=f(f(y+2))=f(f(y+1))=f(y)[/tex] which is a contradiction as [tex]y[/tex] and [tex]y+1[/tex] are in different blocks and so are mapped to different values.
So the blocks must look like [tex]\{1,\ldots,a-1\},\{a\},\{a+1\},\ldots,\{n\}[/tex]. We know that [tex]f(a)=f(f(a+1))[/tex] and since only one value is mapped to [tex]f(a)[/tex] we must have [tex]a = f(a+1)[/tex]. Similarly we can show that [tex]f(a+i)=a+i-1[/tex] for all [tex]i\geq 1[/tex]. Since [tex]f(a-1)=f(f(a))[/tex] we must have [tex]f(a)\in\{1,\ldots,a-1\}[/tex], i.e. [tex]a[/tex] gets mapped to [tex]b[/tex] for some [tex]b<a[/tex]. Finally we know the members of the first block get mapped to some value [tex]c[/tex] which is less than [tex]f(a)=b[/tex]. It is easy to check these conditions are sufficient.
There are [tex]{n\choose 3}[/tex] ways of choosing [tex]a,b,c[/tex] such that [tex]1\leq c<b<a\leq n[/tex] and so [tex]{n\choose 3}[/tex] different maps [tex]f[/tex].
MENU