TechFULの中の人

TechFULスタッフ・エンジニアによる技術ブログ。IT関連のことやTechFULコーディングバトルの超難問の深掘り・解説などを紹介

サイクル分解の標準形【TCB49第7問の背景】

TCB49第7問目では次のような問題を出題しました。

整数 $N, K$ が与えられます。$1, 2, \ldots, N$ の順列 $a$ であって、次の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

  • $a_i = \max(a_1, \ldots, a_i)$ を満たす $i$ の個数が $K$ 個である。
  • $i=1, 2, \ldots, N$ に対して、$a_i \neq \max(a_1, \ldots, a_i)$ または $a_{i+1} \neq \max(a_1, \ldots, a_{i+1})$ が成り立つ。ただし、$a_{N+1}=N+1$とする。

下記リンクから挑戦可能です。TCB終了後のためポートフォリオには反映されません。
techful-programming.com


この記事ではこの問題の背景にある、順列とサイクル分解の標準形の関係についてお伝えします。

順列とサイクルの関係

順列 $a = (a_1, a_2, \ldots, a_N)$ は $w(i) = a_i$ によって定められる $\{1, 2, \ldots, N\}$ から $\{1, 2, \ldots, N\}$ への全単射と見なせます。
次の様に定められるグラフで $w$ を視覚化してみましょう。

  • 頂点 $1, 2, \ldots, N$
  • 辺 $(i, w(i))$ $(1 \leq i \leq N)$

$w$ が全単射であることから、各頂点の入次数と出次数はともに 1 になります。これは、互いに交わらない有向サイクルによってすべての頂点が被覆されていることに他なりません。例えば、$a = (3, 4, 1, 5, 2, 6)$ は

  • $w(1) = 3$
  • $w(2) = 4$
  • $w(3) = 1$
  • $w(4) = 5$
  • $w(5) = 2$
  • $w(6) = 6$

によって定まる写像 $w$ と同一視でき、$w$ を可視化すると、

  • $1 \rightarrow 3 \rightarrow 1$
  • $2 \rightarrow 4 \rightarrow 5 \rightarrow 2$
  • $6 \rightarrow 6$

の三つの有向サイクルに分かれます。この表現をサイクル分解と呼びます。

有向サイクルの表現方法

長さ $l$ のサイクルは、そのサイクルのある元 $c$ から始めると $(c, w(c), w^2(c), \ldots, w^{l - 1}(c)) $ の順に頂点が並んでいます。この列によってサイクルは一意に定まりますが、始点をどれにするか $l$ 通りの自由度があります。そこで、$c$ をサイクルに含まれる頂点のうち、ラベルが最大であるものを選ぶことにすると一意になります。先の例では

  • $1 \rightarrow 3 \rightarrow 1$ は $(3, 1)$
  • $2 \rightarrow 4 \rightarrow 5 \rightarrow 2$ は $(5, 2, 4)$
  • $6 \rightarrow 6$ は $(6)$

と対応付けられます。

サイクル分解の一意な表現

順列はサイクルに分解でき、各サイクルは整数の列と対応付けることができました。この各サイクルを、含まれる頂点番号の最大値の昇順に並べると、サイクル分解の一意な表現が得られます。先の例では三つのサイクル $(3, 1), (5, 2, 4), (6)$ に分解できて、それぞれの最大元はそれぞれの初項 $3, 5, 6$ です。$3 < 5 < 6$ なので最大元の昇順に並べると $\hat{w} = (3, 1, 5, 2, 4, 6)$ が得られます。この列からサイクル分解を復元するには、左から順に元を見ていき、最大値が更新される部分で列を分割すればよいです。つまり、$\hat{w}(k) = \max_{1 \leq i \leq k} \hat{w}(i)$ を満たす $k$ を小さい方から $k_1, k_2, k_3, \ldots$ と置くと、$(\hat{w}(k_i), \hat{w}(k_i + 1), \ldots, \hat{w}(k_{i+1} - 1))$ が一つのサイクルに対応しています。この方法によって長さ $N$ の順列と、$N$ 頂点からなるサイクル分解の一対一対応が得られました。この順列をサイクル分解の標準形と呼びます。

元の問題の言い換え

さて、元の問題に戻りましょう。

  • $a_i = \max(a_1, \ldots, a_i)$ を満たす $i$ の個数が $K$ 個である。
  • $i=1, 2, \ldots, N$ に対して、$a_i \neq \max(a_1, \ldots, a_i)$ または $a_{i+1} \neq \max(a_1, \ldots, a_{i+1})$ が成り立つ。ただし、$a_{N+1}=N+1$とする。

これらの条件は、$a$ をサイクル分解の標準形だと捉えることにより、次の様に言い換えられます。

  • サイクルの個数が $K$ 個である。
  • 長さ $1$ のサイクルが存在しない。

サイクルの指数型母関数を用いることで、数え上げられる形になりました。
長さ $n$ のサイクルは $(n - 1)!$ 個あるので、長さ $1$ のサイクルを除いた指数型母関数は $f(x) = \sum_{i=2}^N (i-1)!x^i / i!$ です。サイクルの集合を取るので、求める値は $\exp(f(x))$ の $x^K$ の係数となります。

ほかの問題との関連

ラベル付き木の数え上げ

頂点 $1, 2, \ldots, N$ からなり、頂点 $1$ を根とする木の総数は $N^{N-2}$ 個あり、ケーリーの公式と呼ばれています。この記事と同様の考えにより示せます。

ある木に対して頂点 $1$ から 頂点 $N$ へのパスを取り、その頂点を並べた列を $(\hat w_1, \hat w_2, \ldots, \hat w_{k})$ と置きます。この $\hat w$ をサイクル分解の標準形とみなすと、

  • 頂点 $1$ を長さ $1$ の閉路とする functional graph
  • 頂点 $N$ を長さ $1$ の閉路とする functional graph
  • その他の頂点からなるいくつかの functional graph

からなるグラフになります。例えば下図の場合だと、左の木の $1, 8, 10, 9, 5, 13$ という頂点列をサイクル分解の標準形 $(1)(8)(10, 9, 5) (13)$と見なして右側の functional graph に変換しています。

逆に、$\{1, 2, \ldots, N\}$ から $\{1, 2, \ldots, N\}$ への写像であって $f(1) = 1, f(N) = N$ を満たす $f$ は $N^{N-2}$ 個あり、$f$ を

  • 頂点 $1, 2, \ldots, N$
  • 辺 $(i, f(i))$ $(1 \leq i \leq N)$

によって可視化すると同様のグラフになります。従って、木の総数は $f$ の個数に等しく、$N^{N-2}$ 個あります。

第一種スターリング数

$N$ 頂点上のサイクル分解であって、$K$ 個のサイクルからなるものの個数を $[{\textstyle{N\atop K}}]$ と置きます。この値は第一種スターリング数と呼ばれており、$$x(x+1)(x+2) \cdots (x+N-1) = \sum_{k = 0}^N [{\textstyle{N \atop k}}]x^k$$が成り立つことが知られています。この記事の考え方で示してみましょう。

$N$ 頂点上のサイクル分解であって、$k$ 個のサイクルからなるものの標準形を次の手順で構成します。

  1. 各サイクルの最大元を合計で $k$ 個決定する。
  2. 最大元以外の頂点 $v$ について、標準形で $v$ より右側にあり、$v < u$ を満たす頂点 $u$ の個数 $f(v) \leq N - v$ を決定する。

このような標準形は、サイクルの最大元のみからなる標準形に、番号の大きい頂点を順に挿入していくことで必ず存在することが示せます。

一方、$x(x+1)\cdots(x+N-1)$ の $x^k$ の係数$$\sum_{1 < a_1 < a_2 < \cdots < a_{n-k} < N} a_1a_2 \cdots a_{n-k}$$は頂点 $N-a_1, N-a_2, \ldots, N-a_k$ がサイクルの最大元にならなかったとき、$f(N-a_1), f(N-a_2) \ldots, f(N-a_k)$ の値が何通りあるかを示しています。従って等式が成り立ちます。