articles3/88c.book(保存済みの内容) … 編集へ / ファイル一覧へ

完全順列の数(Désarménien の対応)
import 88a.book

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+1) = (n+1)\,\mathrm{der}(n) + (-1)^{n+1}\)(88a の der𝕄 から)。

2 最初の下降の列

\(f\) の初めの下降の列 \(f(1) > \cdots > f(a)\) が \(a\) で止まる(\(a = N\) か \(f(a) < f(a+1)\))ことを \(a \in f \,\mathrm{desc}\, N\) と書く。
word(ss,s) … \(\mathrm{desc}\)
desc. … \(f \mathrm{desc} N = \{ a \in \mathbb{M} \mid a \le N , \forall i , x , y \, ( \langle i , x \rangle \in f , \langle ( i + 1 ) , y \rangle \in f , i + 1 \le a \Longrightarrow y < x ) , ( a = N \mathbin{\rm o\!r} \exists x , y \, \langle a , x \rangle \in f , \langle ( a + 1 ) , y \rangle \in f , x < y ) \}\)
列 \(g\) は \(f\) から最後の \(n+1\) 番目を除いたもの。\(g\) の下降の列の止まる所から \(f\) のものが決まる(R1〜R3)。
止まる所はただ1つ。

3 最後の文字を除く

4 減少列

空でない有限個の自然数には最小のものがある。
減少列の最後は最小。
減少列は(最小のものを最後に置いて)作れる。
減少列はただ1つ。

5 数える

\(z \mapsto a\) となる全単射のうち \(f \setminus \{(z,a)\}\) が \(G\) に入るもの全体は、\(G\) と1対1に対応する。
最後の文字を除いても、減少列でなければ「初めの下降の列の長さが偶数」は変わらない(LKa2)。減少列のときは長さ \(n+1\) と \(n\) の偶奇で決まる(LKb2)。
\(S\) を初めの下降の列の長さが偶数の列の全体、\(T\) を最後を除いたものが(残りの値で)その形になる列の全体とする。値ごとに \(\mathrm{der}(n)\) 個なので \(T\) は \((n+1)\,\mathrm{der}(n)\) 個。\(S\) と \(T\) は減少列(\(Z\))だけが違う。

6 主定理

初めの下降の列の長さが偶数の順列(Désarménien の désarrangement)は、完全順列と同じ数だけある。
\(n \in \mathbb{M} \Longrightarrow \{ f \in ( 1 \mathinner{\ldotp\ldotp} n ) \stackrel{\rm IS}\to ( 1 \mathinner{\ldotp\ldotp} n ) \mid \exists a \, \exists h \in \mathbb{M} . a = h + h , a \in f \mathrm{desc} n \} \stackrel{\#}= \mathrm{der} ( n )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ,Ax𝕄 ,ax_s ,+𝕄 ,⋅𝕄 ,AxD

イベント 30 件