Cycle Lemma

数え上げ Cycle Lemma Catalan 数 括弧列 Narayana 数

1. 概要

本記事では，数え上げに関する Cycle Lemma と呼ばれる定理を紹介します．

これはある種の整数列について，列の巡回シフトのうち，累積和が常に正になるものの個数を決定するもので，主張も証明も易しいです．本記事では Cycle Lemma を証明し，そこから多くの有名な数え上げ公式が導出されることを確認します．

2. 前提知識

二項係数の理解を仮定します．

3. Cycle Lemma

3.1. 主張

【定義 1】（累積和）

整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ に対して，その累積和（prefix sum）$S=(S_0,S_1,\ldots,S_N)$ を，$S_n = \sum _ {i=0}^{n-1} A_i$ によって定義する．

$S$ の長さは $N+1$ であり，$S_0=0$ が必ず成り立つことに注意してください．なお文献や文脈によっては $S_0=0$ を除いた列を累積和と呼ぶこともあります．

例えば $A=(1,2,3,4)$ の累積和は $S=(0,1,3,6,10)$ です．

【定理 2】（Cycle Lemma）

整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ が以下の条件を満たすとする．

  • 任意の $i$ について $A_i\leq 1$．
  • 総和を $K$ とすると，$K$ は非負である．

このとき，$A$ の巡回シフトであって，累積和が初項を除きすべて正であるものが，ちょうど $K$ 個存在する．ただし，巡回シフトについては，要素のインデックスを区別する．

言い換えれば，$(A_j,\ldots,A_{N-1},A_0,\ldots,A_{j-1})$ の累積和が初項を除きすべて正であるような $j$ （$0\leq j\leq N-1$）がちょうど $K$ 個存在する．

巡回シフトとは

$A=(A_0,A_1,\ldots,A_{N-1})$ の巡回シフト（cyclic shift）とは，ある定数 $k$ ($0\leq k\leq N-1$) を用いて

$$ (A _ k, A _ {k+1}, \ldots, A _ {N-1}, A_0, A_1, \ldots, A _ {k-1}) $$

と書ける列のことです．例えば $A=(2,3,1,2)$ の巡回シフトは次の $4$ つです．

$$ (2,3,1,2),\quad (3,1,2,2),\quad (1,2,2,3),\quad (2,2,3,1). $$

3.2. 具体例

例えば $A=(1,0,-2,1,-1,1,0,0,1,1)$ とすると，累積和が初項を除きすべて正であるような巡回シフトは $(1,0,0,1,1,1,0,-2,1,-1)$, $(1,1,1,0,-2,1,-1,1,0,0)$ の $2$ つです．

$A$ の巡回シフト 累積和
$(1,0,-2,1,-1,1,0,0,1,1)$ $(0,1,1,-1,0,-1,0,0,0,1,2)$
$(0,-2,1,-1,1,0,0,1,1,1)$ $(0,0,-2,-1,-2,-1,-1,-1,0,1,2)$
$(-2,1,-1,1,0,0,1,1,1,0)$ $(0,-2,-1,-2,-1,-1,-1,0,1,2,2)$
$(1,-1,1,0,0,1,1,1,0,-2)$ $(0,1,0,1,1,1,2,3,4,4,2)$
$(-1,1,0,0,1,1,1,0,-2,1)$ $(0,-1,0,0,0,1,2,3,3,1,2)$
$(1,0,0,1,1,1,0,-2,1,-1)$ $(0,1,1,1,2,3,4,4,2,3,2)$
$(0,0,1,1,1,0,-2,1,-1,1)$ $(0,0,0,1,2,3,3,1,2,1,2)$
$(0,1,1,1,0,-2,1,-1,1,0)$ $(0,0,1,2,3,3,1,2,1,2,2)$
$(1,1,1,0,-2,1,-1,1,0,0)$ $(0,1,2,3,3,1,2,1,2,2,2)$
$(1,1,0,-2,1,-1,1,0,0,1)$ $(0,1,2,2,0,1,0,1,1,1,2)$

3.3. 証明

ところどころ，3.2 の具体例も用いて説明します．

$A=(A_0,A_1,\ldots,A_{N-1})$ を整数列とし，$S=(S_0,S_1,\ldots,S_N)$ をその累積和とするとき，座標平面上の点 $(n,S_n)$ を $n=0,1,2,\ldots,N$ の順に結んでできる折れ線グラフを考えます．

$A$ の巡回シフトは，折れ線グラフを左右に分割して右側・左側の順に結合し，原点から始まるように平行移動することと対応します．

まず，折れ線グラフで $y$ 座標が最小になる位置をひとつとり，そこで $A$ を巡回シフトします．すると，折れ線グラフの $y$ 座標がすべて非負になります．

この状態から条件を満たす巡回シフトの位置を考えると，次の図のような $K$ 箇所となります．

つまり，$y$ 座標が $0,1,\ldots,K-1$ であるような $x$ 座標最大の点です．$A_i\leq 1$ よりこれらの点が存在することに注意してください．

これらの点が条件を満たすこと，これら以外の点が条件を満たさないことはどちらも簡単に証明できるため省略します．（必要であれば解説動画を参照してください．）

4. 応用例

4.1. Catalan 数

Catalan 数にはたくさんの同値かつ重要な定義がありますが，本記事では次の定義を採用します．

【定義 3】（括弧列）

( および ) からなる文字列を括弧列（bracket sequence）という．$S=s_0s_1\cdots s_{N-1}$ を括弧列とするとき，同じ長さの整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ を，$s_i$ が ( ならば $A_i=+1$，) ならば $A_i=-1$ であると定める．この $A$ を $S$ に対応する $\boldsymbol{\pm 1}$ 列と呼ぶ．

【定義 4】（正しい括弧列）

括弧列が正しい括弧列（correct bracket sequence）であるとは，対応する $\pm 1$ 列について，$+1,-1$ が同数含まれ，累積和が常に非負であることをいう．

【定義 5】（Catalan 数）

$N$ を非負整数とするとき，長さ $2N$ の正しい括弧列の個数を $C_N$ と書き，Catalan 数（Catalan number）という．

【定理 6】
次が成り立つ． $$C_N=\frac{1}{2N+1}\binom{2N+1}{N}=\frac{1}{N+1}\binom{2N}{N}.$$

次の $4$ つの数え上げを考えます．

  1. Catalan 数 $C_N$（つまり 【定義 4】 の整数列 $A$ の個数）．
  2. $N+1$ 個の $+1$ と $N$ 個の $-1$ からなる列 $B$ であって，累積和が初項を除きすべて正であるものの個数．
  3. $N+1$ 個の $+1$ と $N$ 個の $-1$ からなる列の個数．
  4. $N+1$ 個の $+1$ と $N$ 個の $-1$ からなる列であって，先頭が $+1$ であるものの個数．

1 の数え上げと，2 の数え上げは等しいです．これは，$A$ の先頭に $+1$ を挿入したものを $B$ とする，という対応から分かります．よって Catalan 数を求めるには 2 の数え上げを求めればよいです．

2 の数え上げと 3 の数え上げは，2 の数え上げの $2N+1$ 倍が 3 の数え上げに等しいという関係になります．これは Cycle Lemma から分かります．このことから $C_N=\frac{1}{2N+1}\binom{2N+1}{N}$ が分かります．

また 2 の数え上げと 4 の数え上げは，2 の数え上げの $N+1$ 倍が 4 の数え上げに等しいという関係になります．これも Cycle Lemma から分かります．このことから $C_N=\frac{1}{N+1}\binom{2N}{N}$ が分かります． $\blacksquare$

4.2. Catalan Convolution Formula

【定理 7】（Catalan Convolution Formula）
$M$ を正整数とする．$N$ を非負整数とするとき，$n_0+n_1+\cdots+n_{M-1}=N$ となる非負整数列 $(n_0,n_1,\ldots,n_{M-1})$ に対する $\prod_{i=0}^{M-1}C_{n_i}$ の総和は次の値となる． $$ \frac{M}{2N+M}\binom{2N+M}{N} $$

注意
この定理で $M=1$ としたものは当然，【定理 6】 と一致します．

また，この定理は，形式的べき級数 $C(x) = \sum _ {i=0} ^ {\infty}C _ ix ^ i$ を用いると，$[x ^ N]C(x) ^ M = \frac{M}{2N+M}\binom{2N+M}{N}$ と表すこともできます．

定理の総和は，次のような数え上げと等しいです：

  • 正しい括弧列に対応する $\pm 1$ 列の $M$ 個組で，長さの総和が $2N$ であるものの個数．

さらに，これら $M$ 個の整数列のそれぞれの先頭に $+1$ を挿入し結合すると，求めるべきは次のようになります．

  • $N+M$ 個の $+1$ と $N$ 個の $-1$ からなる整数列であって，累積和が初項を除き正であるようなものの個数．

Cycle Lemma よりこの数え上げは $\frac{M}{2N+M}\binom{2N+M}{N}$ と一致します．

4.3. Fuss–Catalan 数

【定理 8】

$N,M$ を正整数とする．$NM$ 個の $+1$ および $N$ 個の $-M$ からなる整数列であって，その累積和が常に非負であるものの個数は次の値に等しい：

$$ \frac{1}{NM+1}\binom{NM+N}{N} $$

やはり，先頭に $+1$ を挿入した列を Cycle Lemma で数えます．

$NM+1$ 個の $+1$ および $N$ 個の $-M$ からなる整数列であって先頭が $+1$ であるものを数えて，$NM+1$ で割ればよいので，このようになります． $\blacksquare$

4.4. Narayana 数

【定理 9】（Narayana 数）

$N$ を正整数とし，$M$ を $1\leq M\leq N$ を満たす整数とする．このとき，長さ $2N$ の正しい括弧列に対応する $\pm 1$ 列であって，$(A_i,A_{i+1})=(1,-1)$ を満たす $i$ がちょうど $M$ 個あるものの個数は次の値に等しい：

$$ \frac{1}{N}\binom{N}{M}\binom{N}{M-1} $$

やはり先頭に $+1$ を挿入して Cycle Lemma を用いると，次の数え上げを $N+1$ で割ればよいことが分かります．

  • $N+1$ 個の $+1$ と $N$ 個の $-1$ からなる $\pm 1$ 列 $A = (A _ 0, A _ 1, \ldots, A _ {2N})$ であって，$A_0 = +1$ であり，$A_i = +1, A_{i+1} = -1$ を満たす $i$ がちょうど $M$ 個あるものの個数．

$+1,-1$ の境界で区切ると，この列は次を満たす $a_0,a_1,\ldots,a_M,b_0,b_1,\ldots,b_{M-1}$ の数え上げに対応します．

  • $+1$ が並ぶ個数の列：$a_0 + a_1 + \cdots + a_M = N+1$ を満たす整数 $a_0,a_1,\ldots,a_M$ であって，$\begin{cases}a_i>0 & (0\leq i<M) \\ a_i \geq 0 & (i=M)\end{cases}$ を満たすもの．
  • $-1$ が並ぶ個数の列：$b_0 + b_1 + \cdots + b_{M-1} = N$ を満たす正整数 $b_0, b_1, \ldots, b _ {M-1}$．

したがって求める個数は

$$ \frac{1}{N+1}\binom{N+1}{M}\binom{N-1}{M-1} $$

で，これを式変形すると 【定理 9】 の通りであることが分かります． $\blacksquare$

5. 関連問題

  1. https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota2023spring_final_e
  2. https://yukicoder.me/problems/no/790
  3. https://atcoder.jp/contests/kupc2020/tasks/kupc2020_m
  4. https://atcoder.jp/contests/xmascon22/tasks/xmascon22_d
  5. https://yukicoder.me/problems/no/758
  6. https://yukicoder.me/problems/no/2472
  7. https://atcoder.jp/contests/agc070/tasks/agc070_c
  8. https://yukicoder.me/problems/13022

問題について

1 は Cycle Lemma の理解が直接役に立つ問題です．ただし定理をそのままの形で適用するには，符号を適切にとり操作列を reverse する程度の調整は必要です．

2 は Catalan 数，3，4 は Catalan convolution formula，5，6，7 は Narayana 数が利用できる問題です．

8 は本記事で解説した形の Cycle Lemma そのままではありませんが，おおよそ同じ発想を利用することができる問題です．

6. まとめ

本記事では Cycle Lemma を証明し，応用として Catalan 数などの数え上げを導出しました．

特に Catalan 数は，二分木や三角形分割などのさまざまな数え上げに登場し，重要度が高いです．Catalan 数の導出も Cycle Lemma を使う方法に限らずいろいろな方法があり，AtCoder Algorithm Lectures でも紹介する機会があると思います．

また，Cycle Lemma は，Lagrange 反転公式の組み合わせ的導出にも用いられます．

7. 参考文献

  1. A. Dvoretzky, Th. Motzkin．A problem of arrangements．Duke Mathematical Journal．Vol. 14．No. 2．pp. 305–313．1947．DOI: 10.1215/S0012-7094-47-01423-3．https://doi.org/10.1215/S0012-7094-47-01423-3．
  2. N. Dershowitz, S. Zaks．The Cycle Lemma and Some Applications．European Journal of Combinatorics．Vol. 11．No. 1．pp. 35–40．1990．DOI: 10.1016/S0195-6698(13)80053-4．https://doi.org/10.1016/S0195-6698(13)80053-4．
  3. M. Bona (ed.)．Handbook of Enumerative Combinatorics．CRC Press．2015．https://www.taylorfrancis.com/books/edit/10.1201/b18255/handbook-enumerative-combinatorics-miklos-bona．
  4. Wikipedia．カタラン数．https://ja.wikipedia.org/wiki/カタラン数．（閲覧日: 2026-03-31）．
  5. Wikipedia．Narayana number．https://en.wikipedia.org/wiki/Narayana_number．（閲覧日: 2026-03-31）．
  6. Dardy．[Tutorial] Catalan Numbers and Catalan Convolution．Codeforces Blog．https://codeforces.com/blog/entry/87585．（閲覧日: 2026-03-31）．

トップページ：AtCoder Algorithm Lectures