Skip to content →

順列


inv(w)を順列wの転倒数と置く。
降下集合\(D(w)=\{i:w_i>w_{i+1}\}\)
des(w)=#D(w)
ID=D(w^{-1})
IDはwを数字の昇順に見ていったとき、右から左に戻るときに読んだ要素数の総和の集合と等しい。
\(maj(w)=\sum_{i \in D(w)}i\)

\(\sum_{w \in \mathcal{S}_n} q^{inv(w)} = \sum_{w \in \mathcal{S}_n} q^{maj(w)} =\boldsymbol n!\)
inv, majの母関数がこのようになることは挿入dpで分かる(会長さんの証明)。また、\(inv(w) = maj(\phi(w))\) となる全単射 \(\phi\) が構成できる。
\(w_{n-1} < w_n\) のとき、\(w_{i} < w_{n}\) となる \(i\) が末尾となるように順列を分割して各成分を右に巡回シフト。\(w_{n-1} > w_n\) のとき、\(w_{i} > w_{n}\) となる \(i\) が末尾となるように順列を分割して各成分を右に巡回シフト。このような操作はinvとmajが等しい順列間のbijになる。
\(imaj(w)=maj(w^{-1})\)は\(\phi\)で不変。

\(\sum_{x \in S}q^{f(x)}t^{g(x)}=\sum_{x \in S}q^{g(x)}t^{f(x)}\) となるとき、\(f,g\) は対称結合分布であるという。(inv,maj),(inv,imaj),(maj,imaj)は全て対称結合分布である。

$$\#\{maj(w)=j, imaj(w)=k) = \#\{maj(w)=k, imaj(w)=j)$$
$$\#\{maj(\phi(w))=j, imaj(\phi(w))=k) = \#\{maj(\phi(w))=k, imaj(\phi(w))=j)$$
$$\#\{inv(w)=j, imaj(w)=k) = \#\{inv (w)=k, imaj(w)=j\}$$
$$\#\{inv(w^{-1})=j, imaj(w^{-1})=k) = \#\{inv (w^{-1})=k, imaj(w^{-1})=j\}$$

$$\#\{inv(w)=j, maj(w)=k) = \#\{inv (w)=k, maj(w)=j\}$$

多重集合\(M=\{1^{a_1},2^{a_2},\ldots,m^{a_m}\}\)上の順列全体を \(\mathfrak{S}_M\) と置く。$$\sum_{w \in \mathfrak S_M} q^{inv(w)} = \boldsymbol{n \choose a_1,a_2, \dotsc, a_m}$$

\(\boldsymbol{a_1!a_2!\cdots a_m!}\sum_{w \in \mathfrak S_M} q^{inv(w)} = \boldsymbol{n!}\)
の形を示す。これは、全単射 \(\phi : \mathfrak S_{a_1}\times \mathfrak S_{a_2}\times \cdots \mathfrak S_{a_m}\times \mathfrak S_M \to \mathfrak{S}_n \)であって、左辺の各成分の転倒数の和が右辺の転倒数になるものを構成すれば良い。小さい数から順に割り当てていけば良い。invをmajに変えても同様の式が成り立つ。\(\mathfrak{S}_n\)のときと同様に全単射を作れば示せる。

\(w = w_1 w_2 \cdots w_n \in \mathfrak S_n\) と置く。\(f : [n] \to \mathbb{N}\) が

  • \(f(w_1) \geq f(w_2) \geq \cdots \geq f(w_n)\)
  • \(w_i > w_{i+1}\) ならば \(f(w_i) > f(w_{i+1})\)

を満たすとき f を w-compatible と呼ぶ。任意の \(f : [n] \to \mathbb{N}^0\) について、w-compatible となる \(w \in \mathfrak{S}_n\) が一意に存在する。\(\mathcal{A}(w)\) を w-compatible となる f 全体、\(\mathcal{A}_m(w) = \mathcal{A}_m(w) \cap [m]^{[n]}\) と置く。
$$\#\mathcal{A}_m(w)= \left(\!\!\!{n+1 \choose m-des(w)-1}\!\!\!\right)$$なので
$$\sum_{m \geq 1} \mathcal{A}_m(w)x^m = \frac{x^{des(w)+1}}{(1-x)^{n+1}}$$
となる。\(|f| = \sum_i f(i)\) と置く。\(\sum_{f \in {\mathbb{N}^0}^{[n]}} q^{|f|} = \sum_{w \in \mathfrak{S}_n}\sum_{f \in \mathcal{A}_w} q^{|f|}\) を計算すると、\(\sum_{w \in \mathfrak{S}_n} q^{maj(w)} = \boldsymbol{ n!}\) が得られる。
隣接swapは逆順列では |p_i – p_{j}| = 1ならば swap(p_i, p_j)になる。
辞書順最小という条件は逆行列において、i=1,2,..を貪欲に手前に置くという条件になる。
maj は逆順列において、値の昇順に見ていったときに右から左に戻る直前の添字の値になる。

増加木

順列pが最小値aを用いて、語として \(p_Lap_R\) と書けるとき、p の増加木 \(T(p)\) を、aを根、左子を\(T(p_L)\)、右子を\(T(p_R)\)とした木として定義する。増加木と順列は一対一対応する。
\(a_i\) より小さい要素のうち、最も i の近くにあるものが \(a_i\) の親になる。このようなものはスタックにより線形時間で列挙できるのでデカルト木は線形時間で構築できる。また、O(1)-RMQで線形時間で構築できる。また、オンラインで構築する方法もある。\(a_{n+1}\) を追加したいとする。\(a_n\) に対応する頂点の親を順に辿り、最初に見つけた \(a_n\) より小さいものの子を \(a_{n+1}\) とすればよい。親を辿る回数の合計は順列の長さで抑えられる。\(p_{i-1} > p_i < p_{i+1}\) ならば \(p_i\) は子を二つ持つ。
\(p_{i-1} < p_i < p_{i+1}\) ならば \(p_i\) は右子だけ持つ。
\(p_{i-1} > p_i > p_{i+1}\) ならば \(p_i\) は左子だけ持つ。
\(p_{i-1} < p_i > p_{i+1}\) ならば \(p_i\) は葉である。

ケーリー増加木

子の順序を区別しない多分木に、\([n]\) のラベルを子のラベルが親以上になるように割り当てた木を、ケーリー増加木と呼ぶ。根の子がサイクル分解の標準形の left-to-right minima に対応しているので、\(n + 1\) 頂点のケーリー増加木と \([n]\) 上の順列は全単射の関係にある。この木は \(\phi(i) < i\) を満たす写像 \(\phi : [2, n] \to [n-1]\) と同一視できる。このような写像を後退写像と呼ぶことにする。順列 \(p\) に対して \(a_i = \#\{j : j < i, p_i > p_j\}\) を並べた列 \(I(p) = (a_1, a_2, \ldots, a_n) \) を転倒表と呼ぶ。転倒表は後退写像である。転倒列も後退写像なので、順列と全単射の関係にある。

orderedケーリー増加木

子の順序を区別するケーリー増加木をorderedケーリー増加木と呼ぶことにする。根付き木 \(T\) がorderedケーリー増加木 となるように \([n]\) のラベルを貼る方法は、\(n! / \prod \mathrm{size}(v)\) 通りある。ただし、\(\mathrm{size}(v)\) は \(v\) を根とする部分木のサイズとする。

順列 \(p = p_1p_2 \ldots p_n\) について、\(p_1p_2\cdots p_k\) が \(12\ldots k\) の順列となるような \(k < n\) が存在するとき、\(p\) は分解可能であるという。再帰的に分解を繰り返すことで、任意の順列は、分解不能な順列に一意に分解できる。分解不能な順列の通常型母関数を \(f\) と置くと、$$\sum n!x^n = \frac{1}{1-f}$$ となる。


def perm(a, n):
    if n == 1:
        print(*a)
    else:
        for i in range(n):
            a[i], a[n - 1] = a[n - 1], a[i]
            perm(a, n - 1)
            a[i], a[n - 1] = a[n - 1], a[i]

n が奇数のとき、 id が返ってくる
n が偶数のとき、(1 2 .. n) が返ってくる

n が奇数の時 (1 n) を掛ける。このとき、(1 2 .. n – 1) (1 n) = (1 2 .. n) ができる。
((1 2 .. n)^n = id である。
n が偶数のとき (1 n), (2 n), .., (n n) を順番に掛ける。
このとき、(1 n)(2 n).. (n n) = (1 2 .. n) である。


def perm(a, n):
    if n == 1:
        print(*a)
    else:
        for i in range(n):
            perm(a, n - 1)
            if n % 2 == 1:
                a[0], a[n - 1] = a[n - 1], a[0]
            else:
                a[i], a[n - 1] = a[n - 1], a[i]

\(\mathfrak{S}_n\)の各元は \(s_1, s_2, \ldots,s_{n!}\) のprefixの積を取ることで全て生成できるとする。\(A = (1, 2), (2, 3), \ldots, (n, n+1)\) とすると、\(\mathfrak{S}_{n+1}\) の各元は
\(A, s_1, A^{-1} , s_2, A , s_3, A^{-1}, \ldots,s_{n!}, A\)で生成できる(Steinhaus–Johnson–Trotter algorithm)。

高々\(\sum |a_i-i|\)回の隣接swapで恒等置換にできるので、\(inv(a)<\leq \sum |a_i-i|\).一回の隣接swapで高々2しか\(\sum |a_i-i|\)が減らないので、\(2inv(a)<\geq \sum |a_i-i|\)

差がk以上の2要素の隣接swapを繰り返すことで生成できるもののうち、逆順列が辞書順最小になるものを求めよ。値が小さい方から貪欲に手前に持っていけば良い。1より前にある値は、元々1より手前にあり、かつ、差がK超であるものと一致する。この集合の中で最も値が小さいものに対して再帰的に処理していくとO(nlog(n))になる(AGC001F)。

二つの順列 \(a, b\) が、\(1 \leq i \leq n – 2\) について \(a_i + b_{i + 2} = a_{i + 1} + b_{i + 1}\) を満たすとする。任意の \(i < j\) について \(a_i + b_j = a_{j-1} + b_{i + 1}\) が成り立つ。 従って、\(b_{n + 1} = b_k\) が成り立つとき、\(i = k-1, j = n + 1\) とすると \(a_{k – 1} + b_{k} = a_{n} + b_{k} \Leftrightarrow a_{k-1} = a_n\) となる。\(a\) の要素は相異なるから、\(k = 1\) である。従って、先頭から順に \(x, a_3+b_3, a_4+b_4, a_5+b_5, \ldots\) となるように \(a, b\) を入れ替えていくとよい。

図の2種類しかない。(ref

相異なる[3n]の要素からなるn個の長さ3の列に対して、先頭の要素のうち、最も小さいものを順番に選んで削除していく。選んだ順序で並べると長さ3nの数列ができる。何通りの数列ができるか、O(n^3)で求めよ(AGC043D)。
後ろから見る。

\((1, 2, \ldots, N)\) の順列 \(P\) の転倒数の偶奇(置換の偶奇)は線形で求められます。

辺 \((i, P_i)\) \((1 \leq i \leq N)\) を貼った有向グラフを \(G\) とします。各頂点の入次数・出自数が共に1なので、\(G\) は交わらない有向閉路の和で表せます。頂点数 \(k\) の閉路
\(a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_k \rightarrow a_1\)
に着目します。順列の先頭から \(a_1\) 番目と \(a_2\) 番目を swap すると、自己ループ
\(a_1 \rightarrow a_1\)
と長さ \(k-1\) の閉路
\(a_2 \rightarrow a_3 \rightarrow \cdots \rightarrow a_k \rightarrow a_2\)
に分かれます。従って、長さ \(k-1\) の閉路で再帰的に swap をすると、長さ \(k\) の閉路は、\(k-1\) 回の swap で自己ループ(恒等置換)に分解できます。よって、長さ \(k\) の有向閉路の転倒数の偶奇は \(k-1\bmod 2\) と等しいです。各有向閉路の和を取ると、\(G\) の転倒数の偶奇は (頂点数)−(有向閉路の個数)を \(2\) で割った余りに等しいです。これは、BFS によって線形時間で求められます。実装で楽をしたければ、Union Find でも良いと思います。

長さnの2つの順列a,bが与えられる。任意の \(i \in [n]\) について \(c_i \neq a_i, b_i\) が成り立つ順列 c の個数を求めよ(ABC214G)。a が恒等置換になるようにラベルを張り替えても一般性を失わない。a, b のサイクル分解を考えて、包除原理をする。

連続な添字の集合 \( I = [a, b]\) であって、その像 \(\pi = \{\pi_i : i \in I\}\) もまた連続になるものを区間と呼ぶ。

2つの数列について、順序を保つ全単射があるとき、順序同型と呼ぶ。特に、順序同型な \([n]\) の順列を元の列の簡約形と呼ぶことにする。長さ \(n, m\) の2つの順列 \(\sigma, \tau\) の和を
\(\sigma \oplus \tau = \begin{cases}
\pi(i) & (k\in [1, n])\\
\sigma(i-m)+n & (\text{otherwise})
\end{cases}\) で定義する。また、歪和を
\(\sigma \ominus \tau = \begin{cases}
\pi(i) + m& (k\in [1, n])\\
\sigma(i-m) & (\text{otherwise}) \end{cases}\) で定義する。\((\pi \oplus \sigma)^{-1} = \pi^{-1} \oplus \sigma^{-1}, (\pi \ominus \sigma)^{-1} = \sigma^{-1} \ominus \pi^{-1}\) が成り立つ。

長さ \(m\) の順列 \(\sigma\) と \(k\) 個の非空な順列 \( \theta_1, \theta_2, \ldots, \theta_k\) に対して、膨張 \(\sigma[\theta_1, \ldots, \theta_k]\) を、ブロック \(\theta_1, \theta_2, \ldots, \theta_k\) に分解できる順列であって、それらのブロックを一つの要素とみなしたときに誘導される順列が \(\sigma\) であるものと定義する。\(\sigma\) を分解の商と呼ぶ。任意の順列 \(\pi\) は2つの自明な分解 \(\pi[1, 1, \ldots, 1], 1[\pi]\) を持つ。自明な分解しか存在しない順列を単純であるという。任意の順列 \(\pi\) は一意な単純な商 \(\sigma\) を持つ。仮に、ブロックが3つ以上の相異なる2つの分解が存在したとする。すると、互いに交わるブロック \(A, B\) が存在するが、\(A, B\) の和集合でこれを置き換えられる。従ってブロックが二つの場合に帰着される。また、このことより、商が \(12, 21\) でない限り、\(\pi\) を作る \(\sigma\) の膨張は一意に定まる。例えば単調増加の時は \(1234 = 12[1, 123] = 12[12, 12] = 12[123, 1]\) となって膨張が一意に定まらない。一意にするには、商が \(12\) のときは一つ目のブロックの商が \(12\) でない(\(21\)も同様)という条件を加える必要がある(ref)。順列全体のOGFを \(A\), そのうち商が \(12\) でないものの OGF を \(A^+\), 商が \(21\) でないものの OGF を \(A^{-}\), 単純な順列のうち長さ3以上のものの OGF を \(F\) と置く。\begin{align}
\mathcal{A^+} &= 1 \cup 21[\mathcal{A}^-, \mathcal{A}] \cup \bigcup_{\pi \in \mathcal{F}}\pi[\mathcal{A}, \ldots, \mathcal{A}] \\
\mathcal{A} &= 1 \cup 21[\mathcal{A}^-, \mathcal{A}] \cup 12[\mathcal{A}^+, \mathcal{A}] \cup \bigcup_{\pi \in \mathcal{F}}\pi[\mathcal{A}, \ldots, \mathcal{A}] \\
\end{align}
である。\(B = A^+=A^-\) だから \begin{align}
B&=x+BA+F(A) \\
A&=x+2BA+F(A) \\
\end{align}
となる。\(F\) について解くと \(F = x-A^{-1}(x)-2x^2/(1+x)\) 。商が 12 のときは、商が 12 でない順列の和として一意に表せる。また、商が 21 のときは、商が 21 でない順列の和として一意に表せる。こちらの方法で単純な順列になるまで分解してできる木を代入分解木と呼ぶ。代入分解木は O(n log n) で構築できる。\(\pi(1), \pi(2), \ldots, \pi(k-1)\) によって誘導される代入分解木の部分グラフがすでに構築できているとする。\( \pi(L), \pi(L+1), \ldots, \pi(k)\) が区間であることと、\(k-L+1=\max_{L \leq i \leq k} \pi(i)-\min_{L \leq i \leq k} \pi(i)\) が同値である。これを満たす最大の \(k\) はセグメント木で求まる。

行列の行・列のswapは二部グラフの各部集合の頂点ラベルの張り替えと言い換えられる(ARC107C)。

順列 p に対して、|i-j| = p_i または |i-j| = p_j のとき p_i と p_j を swap できる。ソートする手順を示せ(TTPC2015I)

p_i と p_{i+p_i \pmod n} を swap できる。ソートする手順を示せ(ARC110F)

Gray Code
\((0, 1, \ldots, 2^n-1)\) の順列 p であって、p_i \mathrm{xor} p_{i+1} の bitcount が K となるものを構築せよ。
\(n = k\) でのグレイコード \(p\) が得られているとする。すると、\(p_1, p_2, \ldots, p_{2^k-1}, 2^k+p_{2^k-1}, 2^k+p_{2^k-2}, \ldots, 2^k+p_1\) とすれば \(n = k+1\) でのグレイコードが得られる。\(i\) ビット目は、\(2^i+2^{2i}\mathbb{Z}\) で 1 になるので \(p_i = i \operatorname{xor} \lfloor i / 2 \rfloor\) とすればよい。\(i\mapsto p_i\) は \(\mathbb{F}_2[[x]] / (x^{2^n})\) で \((1+x)\) を掛けることに相当する。\((1+x)^{2^n} = 1\) だからその逆関数は \((1+x)^{-1}(1+x)^{2^n-1} = (1+x)(1+x^2) \cdots(1+x^{2^{n-1}})\) を掛ければよい。これはビット演算で簡単にできる。\(\mathbb{F_2}^{n}\) の基底であって、popcount が K になるものを取れたとする。すると、グレイコードの各ビットにそれぞれの基底を対応させることで、隣接する値の xor の popcount が K になるものが構成できる。K が奇数ならばそのような基底は必ず構成できる。最初の \(K+1\) 個の要素が 1, その他の要素が 0 であるベクトルを \(v\) とする。\(v\) から、ある 1 を 0 にしたベクトル \(K + 1\) 個と、最初の 1 を 0 にしてから、ある 0 を 1 にしたベクトル \(n – K – 1\) 個である(ARC138D)。また、\(p_{2^n}\operator{xor}p_1\) の popcount が 1 であるという条件を無視して、\(A, B\) が与えられるので、\(p_1 = A, p_{2^{n-1}} = B\) となるものを構成せよという問題も考えられる。(AGC31C)
\(a_n = a_{n-1}-a_{n-2}\) の場合を意識して計算していく。
\begin{align}
&a_{n} a_{n-2} a_{n-1}^{-1} = 1 \\
&(a_{n} a_{n-2} a_{n-1}^{-1}) (a_{n-1} a_{n-3} a_{n-2}^{-1}) = 1 \\
&a_{n} a_{n-2} a_{n-3} a_{n-2}^{-1} = 1 \\
&a_{n} a_{n-2} (a_{n-5}a_{n-6}^{-1}a_{n-5}^{-1}) a_{n-2}^{-1} = 1 \\
\end{align}

\(a_na_{n-3} a_{n-4}^{-1} a_{n-1}^{-1}=a_na_{n-2}a_{n-1}^{-1}=1\) より \(a_n a_{n-3} = a_4a_1 = A\) であるから、\(a_nAa_{n-6}A^{-1}=1\). (ref)

超置換

全ての \([n]\) の順列が部分文字列として現れる列を超置換と呼ぶ。\(a = (n,n-1,\ldots, 1), b = (n-1,n)(n-1, n-2, \cdots, 1)^2\) と置く。接尾辞を順列 \(p = p_1p_2 \cdots p_n\) から順列 \(ap\) に変化させるには末尾に \(a_1\) を加えればよい。順列 \(bp\) に変化させるには末尾に \(a_2a_1\) を加えればよい。逆に1文字加えて別の順列に変化させるのは \(a\) 、2文字加えて別の順列に変化させるのは \(b\) だけである。頂点集合を \(\mathcal{S}_n\) とする有向グラフを考える。任意の相異なる頂点 \(u, v\) に対して、有向辺 \((u, v)\) が張られており、その重みは接尾辞を \(u\) から \(v\) にするために末尾に加える必要がある最小の文字数とする。辺集合 \(E_B=\{(\pi, b\pi) : \pi \in \mathcal{S}_n\}\) の各辺について \(\pi\) を \((a^{n-1}b)^i\pi\) で置き換えると移りあうもの同士を同じ色で塗る。頂点は \(a\) を何回か掛けて移り合うものを同じ色で塗る。\(ba^{n-1} = (n-1, n)(n, n-1, \ldots, 1) = (n-1, n-2, \ldots, 1)\) である。\(\operatorname{ord}(a) = n, \operatorname{ord}(ba^{n-1})=n-1\) である。超置換に表れる、重み 2 の辺の色の種類数と重み 3 以上の辺の個数の和は \((n-2)!-1\) 以上である。

  • ある色の頂点を全て訪れた直後の異なる色の頂点への遷移
  • 初めてのある色の辺の遷移

この二つの遷移は重みが2以上である。また、この二つを同時に満たす遷移 \((u, v)\) が存在するならば、\(a^{-(n-1)}u\) への遷移は重み 3 以上である。従って、超置換の長さの下限は \(n-3+n!+(n-1)!+(n-2)!\) であることが分かる(ref)。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA