For a permutation $\sigma\in S_n$ we say i is a strong fixed point, if $\sigma(j)<\sigma(i)$ for $1\leq j<i$ and $\sigma(j)>\sigma(i)$ for$ i<j\leq n$
i) Show a strong fixed point is a fixed point
let i be a strong fixed point. Let us asume $\sigma(i)\neq i \Rightarrow$ there is $j<i$ or $j>i$ with $\sigma(j)=i$. This is in contradiction with the Definition of strong fixpoint.
ii)For $n\geq1$ is $a_n$ let $g(n)$ be the number of permutations in $S_n$ with no strong fixed points. We set g(0)=1
Show that:
$$n!=g(n)+\sum_{j=1}^ng(j-1)(n-j)!$$
$\Leftrightarrow g(n)=n!-\sum_{j=1}^ng(j-1)(n-j)$ I know that $|S_n|=n!$ and let $M_i$ be the set of all permutations with the smallest strong fixed point, then no fixed point can be before j this ist the g(j-1) and after that its allow to have any permutation (n-j)!. Together there are g(j-1)(n-1)!
iii) Show that: $$\sum \limits_{\geq0}g(n)x^n=\frac{F(x)}{1+xFx}$$ and for $F(x)=\sum \limits_{n\geq0}n!x^n$
here i know from ii) what g(n) is. But i dont know how to combine this.
Set :
$$G(x):=\sum_{n\geq 0} g(n)x^n$$
Then you have :
$$n!=g(n)+\sum_{j=1}^ng(j-1)(n-j)! $$
Hence :
$$n!=\sum_{j=0}^{n-1}g(j)(n-j-1)!+g(n) $$
Multiply by $x^n$ and sum over all $n$ :
$$\sum_{n\geq 0}n!x^n=\sum_{n\geq 0}g(n)x^n+\sum_{n\geq 0}\sum_{j=0}^{n-1}g(j)(n-j-1)!x^n $$
On the left you get $F(x)$, on the right you recognize G(x) :
$$F(x)=G(x)+x\sum_{n\geq 0}\sum_{j=0}^{n-1}g(j)(n-j-1)!x^{n-1} $$
With the implicit convention that :
$$\sum_{j=0}^{n-1}g(j)(n-j-1)!$$
is null when $n=0$ :
$$F(x)=G(x)+x\sum_{n\geq 1}\sum_{j=0}^{n-1}g(j)(n-j-1)!x^{n-1} $$
$$F(x)=G(x)+x\sum_{n\geq 0}\sum_{j=0}^{n}g(j)(n-j)!x^{n} $$
We then recognize a Cauchy product :
$$F(x)=G(x)+xG(x)F(x)$$
Hence :
$$G(x)=\frac{F(x)}{1+xF(x)}$$