問題文の条件を満たす任意の長さの順列を良い順列と呼びます。
\(n \geq 1\) における答えの母関数を \(F(x)\) とします。また、

\[G(x) = \sum_{i=0}^\infty i! x^i\]

とします。この時、

\[G(x) = 1 + F(x) + F^2(x) + \dots = \frac{1}{1-F(x)}\]

が成り立ちます。

(証明) 全ての順列 \(p\) について、\(\max_{j \leq i}(p_j) = i\) である場所で \(p\) を切ってみましょう。(たとえば \(p=(2,4,1,3,7,6,5,9,8)\) のとき \((2,4,1,3),(7,6,5),(9,8)\) という要領) このとき、切った後のそれぞれの列は、全体から適切に定数を引くことで、同じ長さの良い順列と一対一対応することができます。
このことから、全ての順列は「良い順列を \(0\) 個以上連ねてできた列」と一対一対応することが示せます。これを母関数で表すと、\(A(x)\) を \(0\) 個以上連ねる操作は \(1+A+A^2+\dots\) に対応することから上式を得ることが出来ます。(証明終わり)

上式を \(F(x)\) の式にすると

\[F(x) = 1 - \frac{1}{G(x)}\]

を得るため、形式的冪級数の逆元を用いればこの問題を解くことが出来ます。