Example
Consider the permutation $\sigma = [1 3 2]\in S_3$ (which is $1\mapsto 1$, $2\mapsto 3$, $3\mapsto 2$). In the standard representation introduced in the exercise, $\sigma = (1)(3,2)$. Now $\hat{\sigma} = [1 3 2] = \sigma$, so $\sigma$ is fixed under $\hat{{}}$.
Solution
Let $A(n)$ be the number of fixed permutations in $S_n$.
We see that $A_1 = 1$ and $A_2 = 2$, i.e. in $S_1$ and $S_2$, all permutationes are fixed.
Now let $n \geq 3$. Let $\pi\in S_n$ be fixed under the transformation. Consider the largest number $n$. In the standard representation, $n$ is the first element of the last cycle.
If the last cycle has length $1$ (i.e. it has the form (n), which is a fixed point), then $\pi$ is fixed if and only if after removing the cycle $(n)$, the resulting permutation is fixed in $S_{n-1}$.
Now assume the last cycle of $\pi$ is $(n,\ldots,a)$ of length $\geq 2$. Then $\hat{\pi}(n) = a$. So also $\pi(n) = a$, which implies that the last cycle is $(n,a)$. Now $\pi(a) = n$ and $\hat{\pi}(n-1) = n$, which implies $a = n-1$. So the last cycle has the form $(n-1, n)$. We see that $\pi = \hat{\pi}$ if and only if after removing the last cycle, the resulting permutation is fixed in $S_{n-2}$.
So $A(n) = A(n-1) + A(n-2)$. Thus $A(n)$ adheres to the same recursion formula as the Fibonacci numbers F(n). Because of $A(1) = 1$, $A(2) = 2$ and $F(2) = 1$, $F(3) = 2$, we get $A(n) = F(n+1)$.
This is quite hand-wavy but I think that's acceptable considering you want intuition. There is $1$ key gap in the result, but maybe someone can come along and fill that in nicely.
First the notation:
$N(n)$ is the number of complete compositions of $n$
$N(n,a)$ is the number of complete compositions of $n$ with $a$ as the largest term
$N(n,a,i)$ is the number of complete compositions of $n$ with $a$ as the largest term and only a single term $i$ that has to be at the end of the sequence.
For each of those, let $\tilde{N}$ denote the set of sequences that fit the description.
For example: $N(5)=8$, $N(5,1)=1$, $N(5,2)=7$, $N(5,2,2)=1$, $N(5,2,1)=1$, $\tilde{N}(5,1)=\{1+1+1+1+1\}$, $\tilde{N}(5,2,2)=\{1+1+1+2\}$, $\tilde{N}(5,2,1)=\{2+2+1\}$
Now we introduce $2$ key relations. The first one:
$$N(n)=\sum_{a=1}^{n}N(n,a)$$
This one should make sense. The total number of complete compositions of $n$, is the number of complete compositions with a maximum term of $1$ + the number of complete compositions with a maximum term of $2$ + etc.
The second one:
$$N(n,a)=\sum_{i=1}^{a}N(n-i,a)+N(n,a,i)$$
To see this, take an arbitrary composition $c\in \tilde{N}(n,a)$. Write $c=c_1+c_2+...+c_m$, and consider the composition $c'=c_1+c_2+...+c_{m-1}$. Now there are $2$ possibilities:
- $c'$ is a complete composition of $n-c_m$ with largest term $a$
- $c'$ is an incomplete composition of $n-c_m$
If $c'$ is a complete composition of $n-c_m$ with largest term $a$, then $c'\in\tilde{N}(n-c_m,a)$.
Otherwise, since $c$ was a complete composition of $n$ with largest term $a$ and $c'$ is not complete, $c_m$ must have been the only term with this value in $c$, so that removing it results in an incomplete composition. Therefore $c'\in \tilde{N}(n,a,c_m)$
You can do this reasoning the other way around as well to establish the claim.
Now we first have to agree that
$$\lim_{n\to \infty}\frac{\sum_{i=1}^{a}N(n,a,i)}{N(n,a)}=0$$
To see this, think about what compositions $\cup_{i=1}^{a}\tilde{N}(n,a,i)$ contains. This set contains all compositions that contain some term exactly once, where that term has to be the last term in the composition. It is 'intuitively clear' that this is an awfully specific subset of $\tilde{N}(n,a)$.
So that we can rewrite*:
$$N(n,a)\approx\sum_{i=1}^{a}N(n-i,a)$$
And now
$$
\begin{aligned}
N(n+1)
& =\sum_{a=1}^{n+1}N(n+1,a) \\
& \approx \sum_{a=1}^{n+1}\sum_{i=1}^{a}N(n-(i-1),a)\\
& = \sum_{a=1}^{n+1}\sum_{i=0}^{a-1}N(n-i,a)\\
& = \sum_{a=1}^{n}\sum_{i=0}^{a-1}N(n-i,a) + \sum_{i=0}^{n}N(n-i,n) \\
& = \sum_{a=1}^{n}[\sum_{i=1}^{a}[N(n-i,a)] + N(n,a) - N(n-a,a)]\\
& = \sum_{a=1}^{n}\sum_{i=1}^{a}N(n-i,a) + \sum_{a=1}^{n}N(n,a) - \sum_{a=1}^{n}N(n-a,a)\\
& \approx N(n) + N(n) - \sum_{a=1}^{n}N(n-a,a)\\
& \approx 2N(n)
\end{aligned}
$$
So now we established that $N(n)$ asymptotically will behave as $c2^n$ for some constant $c$. Now from the fact that the total number of compositions of $n$ equals $2^{n-1}$ we know that $c<\frac{1}{2}$. And from observation we know of course that $c=\frac{1}{4}$. However, I have not really been able to come up with an argument for why it is $\frac{1}{4}$. Maybe it makes sense to say that $c$ must be of the form $\frac{1}{2^m}$ because we do want $N(n)$ to be a whole number. So then all we have to do is it find a reasoning for why $N(n)>2^{n-3}$. So maybe someone who reads this will be able to complete this reasoning from here.
So this might seem like a useless result because we are still left with the question of why this constant is exactly $\frac{1}{4}$. However, with this reasoning we at least see why the ratio converges in the first place.
*A remarkable result of this approximation is that it turns out that $N(n,2)\approx\frac{1+\sqrt 5}{2}F_n$ where $F_n$ is the $n$th fibonacci number. And this approximation is very good (always only either $1$ or $2$ too large).
Best Answer
I tried my own way and got something slightly different - more on that in a second. Let $c(m,n,k)$ be the number of integer compositions with largers part $\le m$ and exactly $k$ parts. Then
$$\sum_n c(m,n,k)x^n=\left.\sum_{p_1=1}^m\cdots\sum_{p_k=1}^m x_1^{p_1}\cdots x_k^{p_k}\right|_{x_1=x_2=\cdots=x_k=x}=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$
and therefore
$$\sum_n c(m,n)x^n=\sum_n\left[\sum_{k\ge1}c(m,n,k)\right]x^n=\sum_{k\ge1}\sum_nc(m,n,k)x^n$$
$$=\sum_{k\ge1}\left(x\frac{1-x^m}{1-x~~~}\right)^k=\frac{\displaystyle x\frac{1-x^m}{1-x~~~}}{\displaystyle 1-x\frac{1-x^m}{1-x~~~}}=\frac{x(1-x^m)}{1-2x+x^{m+1}}.$$
Note that
$$\frac{x(1-x^m)}{1-2x+x^{m+1}}=\frac{1-x}{1-2x+x^{m+1}}-1,$$
so the given answer and mine differ merely by $1$. What's the deal? The reason we need to add $1$ I presume is that $n=0$ has one integer composition, namely the empty set (it is the empty sum). At least that's what OEIS says, I haven't actually seen the textbook's definition/convention for $0$.