Skip to content →

括弧列の性質

平衡括弧列の定義

平衡括弧列には同値な定義が様々あり、どの定義を使うかによって問題の解きやすさは劇的に変わる。平衡括弧列全体を \(\mathcal P\), 長さ \(2n\) の平衡括弧列全体を \(\mathcal P_{2n}\) と置く。

連結と再帰による定義

平衡括弧列とは、空文字列および、次の操作を繰り返すことで生成される文字列である。

  • 二つの平衡括弧列 \(A, B\) を連結した文字列 \(AB\)
  • 平衡括弧列 \(A\) を用いて \((A)\) と書ける文字列

二つ目の操作を \()A(\) に置き換えた時に生成される文字列を負の平衡括弧列と呼ぶことにする。また、元の定義による文字列を正の平衡括弧列と呼ぶことにする。正の平衡括弧列を逆から読むと負の平衡括弧列になる

\(\pm1\)列による定義

\((\), \()\) を \(+1, -1\) に置き換えた数列 \(\delta a\) の累積和 \(a_i = \sum_{k=1}^i \delta a_k\) について
\begin{eqnarray}
\left\{
\begin{array}{l}
a_{i+1} – a_i\in \{+1,-1\} \\
a_i \geq 0 \\
a_{0} = a_{2N} = 0
\end{array}
\right.
\end{eqnarray}が成り立つとき平衡括弧列と定義する。mod 2 で考えると、初めて \(a_i < 0\) となるのは \(i\) が奇数のときだけだと分かる。従って、\(a_{2i + 1} \geq 0\) で十分。\(a_i \geq 0\) を \(a_i \leq 0\) にすると負の平衡括弧列になる。累積和によって定義されていることから、\(\delta a\) の一点更新は \(a\) の区間更新に直すことになる。例えば、i 文字目を ( から ) に変更する操作は、区間 \([i..2N]\) に \(-2\) を足す操作になる。また、i 番目の ( と j 番目の ) を swap する操作は区間 \([i..j)\) に \(-2\) を足す操作になる。
\(0, 2\) 列による言い換え \begin{eqnarray}
\left\{
\begin{array}{l}
t_{i+1} – t_i\in \{0,2\} \\
t_{2i-1} \geq 2i \\
t_{0} = 0 \\
t_{2N} = 2N
\end{array}
\right.
\end{eqnarray} が有効な場合もある。

()の削除による定義

隣接する2文字()の削除を繰り返すことで空文字列にできる文字列を平衡括弧列と定義する。空でない極小な括弧列 \((A_1), (A_2), \ldots, (A_n)\) を用いて \((A_1)(A_2)\ldots (A_n)\) と書ける括弧列を、根の子の部分木が \(A_1, A_2, \ldots, A_n\) の表すそれである木に対応させると、木の問題に言い換えられることがある。

  • LCA(yuki1778)
  • 二乗の木DP(DDCC2016C)

()の削除は、葉の削除に対応する。この木に空文字列を付けてDFSの上り, 下りを(, )に対応させると元の括弧列が得られる。

  • 対応する括弧の添字は偶奇が異なることを示せ。
  • N 箇所を白、N 箇所を黒で塗った長さ2Nの配列について、白と黒がペアになる括弧列が存在することを示せ。(ARC120D)
  • 添字の集合 \(\{1,2,\ldots,N\}\) を2つの集合 A, B に分ける。A の偶数と奇数の個数は等しく、B の偶数と奇数の個数も等しい。A に含まれる添字の位置では { か }, B に含まれる添字の位置では ( か ) となるように平衡括弧列が構成できることを示せ(AGC048B, CF1593G)

経路による定義

(, ) を格子点 \((x, y)\) から \((x, y+1), (x+1, y)\) の移動と対応させる。括弧列を戦闘から読み込んだとき \(x \leq y \) の下、\((0, 0)\) から \((n, n)\) への移動経路になっているならば平衡括弧列と定義する。

45度回転させて、\((x, y)\) から \((x+1, y+1), (x-1, y-1)\) に \(y \geq 0\) の下、移動できるときの \((0, 0)\) から \((n, 0)\) への経路とすることもできる。以下の問題は経路によって視覚的にイメージした方が分かりやすいと思う。

  • 巡回シフトで平衡括弧列にできるか線形で判定せよ (ARC138C)
  • 巡回シフトで平衡括弧列にできるなら、そのうち、辞書順最小のものを求めよ(VK Cup 2015 Round 1 : A)
  • 平衡括弧列となるような置換のうち、並び替え後の添字が辞書順最小のものを求めよ(ARC141C)
  • 平衡括弧列となる部分文字列の個数を求めよ(2018 codeFlyer 本選 C)

\(y \geq 0\) を \(y \leq 0\) にすると負の平衡括弧列になる。任意の非空な括弧列は非空な正の平衡括弧列と非空な負の括弧列を交互に連結した文字列として一意に表せる。

ゲームによる定義

長さ \(2N\) の配列 \(\delta a\) について、先手と後手は交互に次の操作をする。

  • 先手はまだ選ばれていない要素のうち、最も先頭に近いものを ( に置換する。
  • 後手はまだ選ばれていない要素から好きなものを ) に置換する。

それ以上操作できなくなったときに生成される文字列を平衡括弧列と定義する(ARC138C)

平衡括弧列の個数

長さ \(2n\) の平衡括弧列は $$\frac{1}{n+1}{2n \choose n}$$個ある。この数を \(n\) 項目のカタラン数と呼ぶ。(, ) がそれぞれ \(n\) 個ある長さ \(2n\) の括弧列は \({2n \choose n}\) 個ある。これら全体を \(\mathcal{A_n}\)、長さ \(2n\) の平衡括弧列全体を \(\mathcal{B_n}\) とすると、ちょうど \(|\mathcal{A_n}| = (n + 1)|\mathcal{B_n}|\) であるから、何らかの \(\mathcal{A_n}\) 上の同値関係 \(\sim\) を取ると

  • 同値類のサイズがそれぞれ \(n + 1\) となり、\(\mathcal{A_n}/\sim\) と \(\mathcal{B_n}\) の間の全単射がある。
  • 同値類のサイズがそれぞれ \(\frac{1}{2n+1}{2n + 1\choose n}\) となり、ある同値類と \(\mathcal{B_n}\) の間の全単射がある。

のようなことが成り立つはずである。導出 3, 4 ではそのような同値関係を構成している。

カタラン数の導出1(鏡像法)

長さ \(2n\) の平衡括弧列は、\(y = x + 1\) を通らずに \((0, 0)\) から \((n, n)\) に移動する経路に対応付けられた。その経路数は鏡像法によって、\({2n \choose n}-{2n \choose n-1}\) だと分かる。\(y = x + A\) を通らずに移動する経路数は同様に鏡像法により \({2n \choose n}-{2n \choose n-A}\) である。先頭 \(A-1\) 文字が ( である長さ \(2n+A-1\) 文字の平衡括弧列の個数に等しい。

カタラン数の導出2(組合せ)

(, ) がそれぞれ \(n\) 個ある長さ \(2n\) の括弧列全体を \(\mathcal{A_n}\)、長さ \(2n\) の平衡括弧列全体を \(\mathcal{B_n}\) とする。また、\(1, -1\) がそれぞれ \(n-1, n+1\) 個ある括弧列全体を \(\mathcal{C}_n\) とする。非平衡括弧列 \(\mathcal{A}_n \setminus \mathcal{B}_n \) と \(\mathcal{C}_n\) の間の全単射を作る。

全単射(対合) : 累積和が初めて \(-1\) になった箇所を \(k\) 文字目として、\(k + 1\) 文字目以降の正負を反転させる。
カタラン数は \(|\mathcal{B}_n| = |\mathcal{A}_n|-|\mathcal{C}_n| = {2n \choose n}-{2n \choose n-1}\) となる。

カタラン数の導出3(Bertrand’s ballot theorem)

\(+1, -1\) がそれぞれ \(n+1, n\) 個の列 \(\delta a\) は \({2n+1 \choose n}\) 個ある。部分列 \(\delta a_2, \delta a_3, \ldots, \delta a_{2n+1}\) が平衡括弧列になるには、\(\min a_i = 1\) でなくてはならない。\(\delta a\) の cyclic shift しのうち、そのような条件を満たすのは、\(\min a_i\) を達成する最後の位置を始点に持ってくる場合だけである。\(n, n+1\) が互いに素なことから、cyclic shift で移る列は相異なる。従って、cyclic shift で移り合う列全体を同値類とみなすと、平衡括弧列の個数は $$\frac{1}{2n+1}{ 2n+1 \choose n} = \frac{1}{n+1}{2n \choose n}$$ 個である。

カタラン数の導出4(Chung-Feller) :

Young-Ming Chenによる証明。

  • \(\varphi^{} : L)A(R \mapsto A(L)R\)
    • \(L\) は平衡括弧列、\(A\) は負の平衡括弧列
  • \(\varphi^{-1} :A(L)R \mapsto L)A(R\)
    • \(L\) は平衡括弧列、\(A\) は負の平衡括弧列

上記の \(\varphi, \varphi^{-1}\) は互いに逆写像の関係にあり、\(\varphi\) を作用させると負の平衡括弧列の長さが \(2\) 減る。従って、負の平衡括弧列の長さで同値類を作ると、各同値類の大きさは等しい。平衡括弧列は負の平衡括弧列の長さが \(0\) の同値類をなすから、\(\frac{1}{n+1}{2n \choose n}\) 個ある。

カタラン数の導出5(母関数)

平衡括弧列となる極小な接尾辞を \((A)\) 、残りの文字列を \(B\) とすると、\((A)B\) の形になる。\(A, B\) もまた平衡括弧列だから、\(A\) と \(B\) の長さを \(2i, 2(n-i-1)\) とすると
$$C_{n}=\sum_{i=0}^{n-1} C_i C_{n-1-i}, \quad C_0 = 1$$ が成り立つ。カタラン数の母関数を \(f(x):=\sum C_ix^i\) と置く。漸化式の両辺に \(x^n\) を掛けて \(n \geq 1\) について和を取ると、$$f(x)-1 = xf(x)^2$$ となる。\(f(x)\) について解くと \(f(x) = \frac{1 \pm \sqrt{1-4x}}{2x}\) を得る。\([x^0] f(x) = 1\) より \(f(x) = \frac{1- \sqrt{1-4x}}{2x}\) である。二項定理によって展開すると、\begin{align}
f &= -\frac{1}{2}\sum_{i=1}^\infty {\frac{1}{2} \choose i}(-4)^ix^{i-1} \\
&=\sum_{i=1}^\infty -\frac{1}{2}\frac{1}{2}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right) \cdots \left(-\frac{2i-1}{2}\right)(-4)^i\frac{1}{i!}x^{i-1} \\
&=\sum_{i=1}^\infty\frac{1}{2}\cdot1\cdot3\cdot5\cdots (2i-1) 2^i \frac{1}{i!} x^{i-1} \\
&=\sum_{i=1}^\infty\frac{1}{2}\frac{(2i)!}{i!i!} x^{i-1} \\
&=\sum_{i=1}^\infty C_{i-1} x^{i-1} \\
\end{align} となる。

カタラン数の畳み込み

k 個畳み込んだカタラン数を
$$C_{n, k}=\sum_{n=\sum_{i=1}^k n_i} \prod_{i=1}^k C_{n_i}$$
と置く。例えば \(C_{n,4}\) は平衡括弧列 \(A, B, C, D\) (空文字列を許す) の組であって、長さの和が \(2n\) であるものの個数に等しい。

\(n\) 個の ( と \(n+k\) 個の ) とからなる括弧列全体を \(\mathcal{A}_{n, k}\) と置く。\(\mathcal{A}_{n, k}\) の各元は \(k\) 個の平衡括弧列 \(A_1, A_2, \ldots, A_k\) を用いて \( A_1)A_2)\ldots )A_k\) と一意に書ける。逆に \(k\) 個の平衡括弧列 \(A_1, A_2, \ldots, A_k\) は間に ) を挿入することで \(n\) 個の ( と \(n+k\) 個の ) からなる括弧列になる。

鏡像法などにより $$C_{n, k}=|\mathcal{A}_{n, k}| = {2n+k-1 \choose n}-{2n+k-1 \choose n-1} = \frac{k}{n+k}{2n+k-1 \choose n}$$ となる(KUPC2020M, yuki1662)

\(0 < a_1 < a_2 < \cdots < a_k < n\) を満たす整数列 \(a\) の個数を数える際に、
$$0 \leq a_1-1 \leq a_2-2 \leq \cdots \leq a_k-k \leq n
-k-1$$
として \( < \) を \(\leq\) に直す技術に似ていると思う。

非平衡括弧列

非平衡括弧列 \(S\) は平衡括弧列 \(A_1, A_2, \ldots, A_n\) を用いて $$S = A_1)A_2)\ldots)A_k(\ldots(A_{n-1}(A_n$$ の形に一意にできる。括弧列に何らかの操作をして、平衡括弧列にするための最小操作数は、この形で考えると見通しが良いことが多い。括弧列 \(A,B\) に対応する \(\pm 1\) 列を \(\delta a, \delta b\) とする。上記の形における ) の個数は \(-\min a_i\) に等しく、( の個数は \(a_{2N}-\min a_i\) に等しい。\(b\) も同様。両方が 0 になると平衡括弧列である。\(AB\) に対応する \(\pm 1\) 列を \(\delta c\) とすると、
\begin{align}
&c_{2N} = a_{2N} + b_{2N} \\
&\min c_i = \min(\min(a_i), a_{2N}+\min(b_i))
\end{align}
となる。従ってモノイドになり、セグメント木に乗る。

  • 平衡括弧列となる部分列の長さの最大値
  • 平衡括弧列となるために必要な最小の削除回数
  • 平衡括弧列となるために必要な最小の次の操作数:区間を選び、並びを逆にした後、( を ) に、) を ( にする(CodeSprint13D, SRM688Div1Easy)
  • ?, (, ) からなる文字列について、? を置き換えることで平衡括弧列にできるか。(MUJIN2016D)
    • この問題については、0, 2 列で考える方針も良いと思う。


いくつかの文字列を並び替えて連結したあと、平衡括弧列になるように削除すべき文字の個数は次のように最小化できる。

\(\sum a_i \geq 0\) ならば \(\min(a_i)\) の降順につなげる。
\(\sum a_i \leq 0\) ならば \(\min(a_i)\) の昇順につなげる。

(ABC167F, AOJ2681, yuki684)

非平衡括弧列は、正の平衡括弧列と負の平衡括弧列が交互に現れる列として一意に表せる(ARC141C)。

ベクトル

平衡括弧列の \(\pm 1\) 列は \(2N\) 次元のベクトルと捉えるとよいことがある。平衡括弧列の区間は \(\mathbb{F}_2\) 係数 \(2N\) 次元ベクトル空間の部分空間をなす。例えば \(a \leq b \leq c \leq d\) について、\(S[a .. c]\) と \(S[b..d]\) が平衡括弧列ならば、\(S[a..b), S[b..c], S(c..d]\) は平衡括弧列である(SRM688Div1M)。二つの平衡括弧列の \(\pm 1\) 列 \(\delta a, \delta b\) について、\(\delta c=\delta a-\delta b\) は \(\pm2, 0\) からなる列で、\(c_1=c_{2N}=0\) である。逆に、\(c_1=c_{2N}=0\) を満たす任意の \(\pm 2, 0\) からなる列 \(c\) からある平衡括弧列の \(\pm 1\) 列 \(\delta a, \delta b\) が構成できる(CODE FESTIVAL 2017 Elimination Tournament : C)

交換定理

任意の相異なるバランスの取れた2つの括弧列 \(A, B\) は、A のある二つの文字をスワップすることで編集距離を2小さくできる。

最大重み括弧列問題

  • \(i\) 文字目が ( ならば \(p_i\) 点、) ならば \(-p_i\) 点を得る。長さ \(2N\) の平衡括弧列の場合、得点は最大何点か(えこってさんの提出)。
    (, ) を \(1, -1\) で置き換えた数列を \(\delta a\), \(0, 2\) で置き換えた数列を \(\delta b\) とすると、\(p \cdot \delta a = p \cdot \delta b-2N\) なので、\(p\) と \(\delta b\) の内積の最大値を求めればよい。交換定理より、どの二つの文字をスワップしても重みが小さくなるような括弧列が求めるべきものである。従って、\(p_i\) の大きい順に採用できるか見ていく貪欲法が回る。また別の方法として、\(i=1,3,5,\ldots,\)に対して、順に \(b_i \geq i+1\) を満たすまで、\(1,2,\ldots, i\) のうちまだ採用していない添え字であって、\(p_i\) 最大のものを ( に置き換える方法もある。
  • (, ), x からなる長さ \(2N\) の文字列であって、x を除くと、平衡括弧列になる文字列を考える。\(i\) 番目が ( ならば \(p_i\) 点、x ならば \(0\) 点、) ならば \(-p_i\) 点を得る。最大何点を得るか(ABC250G)。(, x, ) を \(0, 1, 2\) に置き換えた数列を \(\delta s\) とすると、問題の文字列の条件は
    \begin{eqnarray}
    \left\{
    \begin{array}{l}
    s_{i+1} – s_i\in \{0,1,2\} \\
    s_i \geq i \\
    s_{0} = 0 \\
    s_{2N} = 2N
    \end{array}
    \right.
    \end{eqnarray}と言い換えられる。\(s, p\) の内積を最大化すればよい。\(\delta s\) を \(0\) で初期化する。明らかに、\(i=1, 2, \ldots, \) について順に \(s_i \geq i\) が等号で成り立つまで、まだ2回採用していない \(1, 2, \ldots, i\) のうち \(p_k\) が最大のものを選び、\(a_k \leftarrow a_k + 1\) とすればよい。

平衡括弧列のなす束

長さ \(2n\) の平衡括弧列 \(a, b\) について、\(a_i \leq b_i\) \((1 \leq i \leq 2n)\) のとき \(a \leq b\) と定める。このとき、\((a \lor b)_i = \max(a_i, b_i), (a \land b)_i = \min(a_i, b_i)\) となって束をなす(ref)。この束は、山がただ一つの平衡括弧列(位置も持つ)の集合の順序イデアルの束としてみなせるから、Birkhoffの表現定理より、分配束である。分配束なので、階層的である。ランクは転倒数(パスの面積)に等しい。転倒数が減少するような隣接要素の swap を繰り返すことで括弧列 a を b にできるとき、\(a < b\) として定めたposetと捉えることもできる。隣接要素に限らない swap を許すような poset も考えることができるが、これは束ではない。((()))() ∨ ()((())) が ((())()) か (()(())) で定まらない。

様々な全単射

\(A,B,C,D,F \in\mathcal P\) とする。
接頭辞和が負になることのある、(, )が同数含まれる括弧列と、接頭辞和が一度も負にならず、(の方が)より正の偶数個多い括弧列との間の全単射は \(A)B)C(D(E \leftrightarrow A)B)C)D)E\) で構成できる。任意の接頭辞和が非負かつ先頭以外で
零になることのある括弧列と、接頭辞和が先頭以外では正の括弧列との間の全単射は
\((A)B(C(D \leftrightarrow (A(B(C(D\)でできる(ref

Published in データ構造

Comments

コメントを残す

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

CAPTCHA