Désarménien（1982）：初めの下降の列 \(f(1) > \cdots > f(a)\) の長さ \(a\)（＝最初の上昇の位置）が偶数の順列は、完全順列と同じ数だけある。最後の文字を除くと \(k_{n+1} = (n+1)k_n \pm 1\) となり、\(\mathrm{der}\) と同じ漸化式を満たすことから示す。

1 準備

\(\mathrm{der}(n)\) は \(n\) 個の集合の完全順列（どの元も動かす置換）の個数。
word(s,s)F … \(\mathrm{der}\)
AxD … \(n \in \mathbb{M} \Longrightarrow \mathrm{der} ( n ) \in \mathbb{M} , \mathrm{der} ( n ) \stackrel{\#}= \{ f \in n \stackrel{\rm IS}\to n \mid f \cap \text{id} _ n = \emptyset \}\)
Lid∅ … \(f \cap \text{id} _ X = \emptyset \Longleftrightarrow \forall w \in X . \langle w , w \rangle \notin f\) \(\blacktriangleleft\) \(\mathbb{W}.\)
個数の等しい集合の完全順列は、個数が等しい。\(f \mapsto h \circ f \circ h^{-1}\) が全単射になる。

1つの値ごとに数える。
\(X = Y \cup \{z\}\)（\(z \notin Y\)）の完全順列で \(z \mapsto a\) のもの全体 \(F\) を数える。
\(z\) と \(a\) を入れ替える \(t\) を合成した \(t \circ f\) は \(z\) を動かさないので、\(Y\) の置換で動かない点が高々 \(a\) のものと1対1に対応する。
\(z \in X\) とする。\(X\) の完全順列の全体 \(S\) は集合で、\(z\) の行き先 \(a \in X \setminus \{z\}\) ごとの部分がどれも \(q\) 個なら、\(S\) は \(q \cdot k\) 個（LΣ）。
\(0\) 個の集合（空集合）の完全順列は空写像だけなので \(\mathrm{der}(0) = 1\)。
\(1\) 個の集合の置換は恒等写像だけなので、完全順列は無く \(\mathrm{der}(1) = 0\)。
\(n+2\) 個の集合 \(X\) の点 \(z\) をとり、行き先 \(a\) ごとに LF で数え、LD で足し合わせる。

2 主定理

完全順列の個数の漸化式。\(n+2\) 個の集合の点 \(z\) の行き先 \(a\) ごとに数える（LPs）。
der𝕄 … \(\begin{cases} \mathrm{der} ( 0 ) = 1 \\ \mathrm{der} ( 1 ) = 0 \\ n \in \mathbb{M} \Longrightarrow \mathrm{der} ( ( n + 1 ) + 1 ) = ( \mathrm{der} ( n + 1 ) + \mathrm{der} ( n ) ) \cdot ( n + 1 ) \end{cases}\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，Ax1 ，Ax+ ，Ax⋅ ，AxD