Number of monotonic functions which are either only increasing or only decreasing from the set {$1,2,3,4,5,6,7$} to itself should be $2* \binom{13}{6}$ , but what about the those functions for which $f(x) \leq x$ for all $x$ or $f(x) \geq x$ for all $x$ ? I think its should be done recursively but i am not getting it properly. My method was checking small cases like 2 numbers it would be $f(1) = 1$ ,$f(2)=2$ , or $f(1)=2$ ,$f(2)= 2$ for case of $f(x) \geq x$.
Number of monotonic functions satisfying the given conditions
combinatoricsfunctions
Related Solutions
To prove statement A, let $x > y$. Then, as we know, $f(x) > f(y)>0$ and $g(x) > g(y)>0$. Hence, the following chain of statements proves the claim: \begin{gather} f(x) > f(y) \implies g(x)f(x)> g(x)f(y) \quad(\because g(x)>0)\\ g(x) > g(y) \implies g(x)f(y) > g(y)f(y) \quad(\because f(y)>0)\\ g(x)f(x)> g(x)f(y) > g(y)f(y) \implies fg(x) > fg(y) \end{gather}
An analogous proof would follow for part B if $f$ and $g$ were increasing, with a caveat:let $x > y$. Then, as we know, $f(x) > f(y)$ and $g(x) > g(y)$. Hence, the following chain of statements proves the claim: \begin{gather} f(x) > f(y) \implies g(x)f(x)< g(x)f(y) \quad(\because g(x)<0)\\ g(x) > g(y) \implies g(x)f(y) < g(y)f(y) \quad(\because f(y)<0)\\ g(x)f(x)< g(x)f(y) < g(y)f(y) \implies fg(x) < fg(y) \end{gather}
Now, let us see if the same logic could work with part A':let $x > y$. Then, as we know, $f(x) < f(y)$ and $g(x) < g(y)$. Hence, the following chain of statements proves the claim: \begin{gather} f(x) < f(y) \implies g(x)f(x)< g(x)f(y) \quad(\because g(x)>0)\\ g(x) < g(y) \implies g(x)f(y) < g(y)f(y) \quad(\because f(y)>0)\\ g(x)f(x)< g(x)f(y) < g(y)f(y) \implies fg(x) < fg(y) \end{gather}
That's brilliant, so great intuition for anticipating part A'. Now we will check part B':let $x > y$. Then, as we know, $f(x) < f(y)$ and $g(x) < g(y)$. Hence, the following chain of statements proves the claim: \begin{gather} f(x) < f(y) \implies g(x)f(x)> g(x)f(y) \quad(\because g(x)<0)\\ g(x) < g(y) \implies g(x)f(y) > g(y)f(y) \quad(\because f(y)<0)\\ g(x)f(x)> g(x)f(y) > g(y)f(y) \implies fg(x) > fg(y) \end{gather}
And therefore part B' is also done. Note the above logic carefully, I think all steps are equally important.
Use this logic, and see why in most cases, one increasing and one decreasing function doesn't tell you much about the product itself.
Permit me to remark on the connection to Analytic Combinatorics. It is known that all endofunctions on $[n]$ are sets of cycles of labeled trees. This follows from the fact that when we iterate $f$ we obtain a path that terminates in a cycle and is documented in Random Mapping Statistics by P. Flajolet, where the asymptotics are then derived. The construction also appeared at this MSE link. The combinatorial class is then given by
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{F} = \textsc{SET}(\textsc{CYC}(\mathcal{T})) \quad\text{where}\quad \mathcal{T} = \mathcal{Z} \textsc{SET}(\mathcal{T}).$$
Now in the present case there can be no cycles of two or more elements because the values on those cycles would not fit the condition that $f(f(x)) = f(f(f(x))).$ This leaves sets of trees, with the root of the tree being a fixed point. Observe that any leaf with a path to the root including the root that contains more than three nodes also breaks the requirement that $f(f(x)) = f(f(f(x))).$ This restricts the class of trees to those where the path from every leaf to the root including the root contains at most three nodes. Now to characterize these trees they are first, a singleton node (fixed point) or second, a singleton node (also a fixed point) with a set of subtrees attached to it, which are in turn either leaves or have a set of leaves attached to them. With the combinatorial class $\mathcal{T}$ of these trees we thus obtain
$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
The desired combinatorial class $\mathcal{F}$ is a forest of these trees given by
$$\mathcal{F} = \textsc{SET}(\mathcal{T}) = \textsc{SET}(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z}))).$$
Observe that the distinction between nodes that have no subtrees attached to them and nodes with a set of subtrees as a feature which appears during the study of the problem givens is not essential here and we may use the convenient fact that
$$\mathcal{E} + \textsc{SET}_{\ge 1}(\mathcal{Q}) = \textsc{SET}(\mathcal{Q}).$$
We thus have for the class in question that it is
$$\mathcal{F} = \textsc{SET}(\mathcal{Z}\textsc{SET}(\mathcal{Z} \textsc{SET}(\mathcal{Z}))).$$
What is happening here is that for rooted trees of height at most $h$ we have $\mathcal{T}_{\le 0} = \mathcal{Z}$ and for $h\ge 1$
$$\mathcal{T}_{\le h} = \mathcal{Z} \textsc{SET}(\mathcal{T}_{\le h-1}).$$
We instantly obtain the EGF
$$F(z) = \exp(z\exp(z\exp(z))).$$
Extracting coeffficients here we find
$$n! [z^n] F(z) = n! [z^n] \sum_{q=0}^n \frac{1}{q!} z^q \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \sum_{p=0}^{n-q} \frac{1}{p!} q^p z^p \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p [z^{n-q-p}] \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$
This is the formula that is presented at OEIS A000949. Apparently they chose to simplify by omitting the term for $q=0$ ($q^p=1$ only when $p=0$ but then $p^{n-q-p} = 0$) and extracting the term for $q=n$ (which simplifies to $1$) to get
$$1 + n! \sum_{q=1}^{n-1} \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$
Best Answer
First, let us deal with the functions $f:\{1,\dots,7\}\to \{1,\dots,7\}$ which are weakly increasing and satisfy $f(x)\le x$. Imagine graphing such in the Cartesian plane, meaning we plot the seven points of the form $(x,f(x))$ for $x\in \{1,\dots,7\}$. All of the points will lie in the right triangle $T$, whose vertices are $(1,1)$, $(7,1)$, and $(7,7)$.
There is another kind of famous combinatorial problem involving the lower half of a square in a rectangular grid. It is well known that the Catalan numbers count the number of lattice paths, where each step is one unit up or one unit to the right, from $(1,1)$ to $(n,n)$, such that the path stays weakly below the line $y=x$. You can find a bijection from the set of such lattice paths from $(1,1)$ to $(7,7)$, to the set of functions $f:\{1,\dots,7\}\to \{1,\dots,7\}$ under the given conditions.
Here is an example of the bijection I had in mind when $7$ is reduced to $3$. I am writing the functions $f:\{1,2,3\}\to \{1,2,3\}$ as a list, $(f(1),f(2),f(3))$.
Paths:
Functions:
$$ (1,1,1)\quad (1,1,2)\quad(1,1,3)\quad(1,2,2)\quad(1,2,3) $$
Finally, what happens when you change the condition $f(x)\le x$ to the condition $f(x)\ge x$? This time, the graph of $f$ will lie in the triangle $U$ whose vertices are $(1,1)$, $(1,7)$ and $(7,7)$. This is congruent to triangle $T$, and there is a simple bijection taking the graph of a function which fits in $T$ to the graph of a function that fits in $U$; just rotate it $180^\circ$ around the midpoint of the long edge of $T$. You should plot all of the functions for the smaller $\{1,2,3\}$, once for the $f(x)\le x$, once for the $f(x)\ge x$ version, to convince yourself they really are $180^\circ$ rotations of each other. Therefore, the two variants have the same solution.