ブログ名

競技プログラミングやお歌のお話をする高菜です。

ベル数でお馴染みの指数型母関数の exp がどのような数え上げに対応しているのか、どのようなタイプの問題が解けるのかを解説していきます。

$$ \newcommand {\braced} [1] {\left \lbrace #1 \right \rbrace} \newcommand {\bracked} [1] {\left \lbrack #1 \right \rbrack} $$

指数型母関数といえば、添字のシフトが微分になったり、二項係数で重み付けられたコンボリューションが積になったりなどの性質が知られていますね。定義は知っているけれども使い所がワカラナイ! そもそもベル数の指数型母関数が exp 二重になっていてなんだかキモチワルイ! そんなあなたのために本日お授けしたいのがこちら、指数型母関数の exp です。

この記事では指数型母関数の exp がどのような数え上げに対応しているのかを解説し、どのようなタイプの問題が解けるのかをご紹介いきます。いわゆる集合分割とかベル数とかそういうのです。記事の最後でもお話しているのですが、そこそこ出ている印象なのにいざ探したら全然見つからなくて泣きました。(なので、問題の類型だけご紹介して中身が空という寂しい状況に……です。)

記法

  • $\mathbb N$: $0$ 以上の整数全体の集合
  • $\mathbb N _ +$: $1$ 以上の整数全体の集合
  • $\bracked N$: $N$ 元集合 $\braced {1, \dots, N}$

やりたいこと

$N$ 元集合 $\bracked N$ の分割を、ある条件を満たす重みで重みづけて数え上げたいです。その条件とは、分割 $\mathcal A \vdash \bracked N$ の重みが分割成分に関する積に分解し、さらに分割成分の重みが分割成分の要素数のみで決まることです。なお重みの値域は $1$ 以上 $N$ 以下の整数が可逆であるような環ならばなんでもよいのですが、ここでは $R$ とおいておきましょう。例えば有理数体 $\mathbb Q$ や、$N$ より大きな素数 $p$ に対応する有限素体 $\mathbb F _ p$ などはこれを満たしますね。

問題設定

まず重みを定義しましょう。$R$ 上の数列 $\left ( f _ j \right ) _ { j = 1 } ^ { \infty }$ を用いて、分割 $\mathcal A \vdash \bracked N$ の重みを $w ( \mathcal A) = \prod _ { A \in \mathcal A } f _ { \lvert A \rvert }$ で定めます。さらにこの数列に対応する指数型母関数を $f ( x ) = \sum _ { j = 1 } ^ { \infty } \frac { f _ j } { j ! } x ^ j$(ただし、$x$ は不定元です。)と定めます。$j$ が $1$ このとき知りたいものは $\hat f _ N = \sum _ { \mathcal A \vdash \bracked N } w ( \mathcal A )$ なのですが、こちらも $N$ に関する数列と見做して指数型母関数 $\hat f ( x )$ を考え、こちらを計算することにしましょう。代入して、結局知りたいものはこちらです。

$$ \hat f ( x ) = \sum _ { N = 0 } ^ { \infty } \frac { \hat f _ N } { N ! } x ^ N = \sum _ { N = 0 } ^ { \infty } \frac { x ^ N } { N ! } \sum _ { \mathcal A \vdash \bracked N } \prod _ { A \in \mathcal A } f _ { \lvert A \rvert } $$

この問題に該当する最も基本的な例としてベル数 $B _ N$ があります。ベル数は $N$ 元集合の分割の総数のことなのですが、これはすなわち任意の分割 $\mathcal A$ の重みが $1$ とした場合ですね。この重みは当然今回の条件に適合しており、$f _ j = 1 \ ( j \in \mathbb N _ +)$ により定まる数列で作ることができるため $f ( x ) = e ^ x$ です。またよく知られているように、ベル数の指数型母関数は $e ^ { e ^ x - 1 }$ ですから、これと整合するような結果になっていただかないと困りますね。以下計算していきましょう。

答えと解き方

いきなりですが、答えです。 

$$ \hat f ( x ) = \exp f ( x ) $$

計算方法1:漸化式から微分方程式を立てる

$N \in \mathbb N$ に対して $\hat f _ { N + 1 }$ を $\hat f _ N$ で表しましょう。$N + 1$ 元集合として $\lbrack N \rbrack$ に別の点 $\star$ を追加した集合 $\lbrack N \rbrack \sqcup \lbrace \star \rbrace$ を考えて、その任意の集合分割を $\star$ を含む分割成分とそれ以外に分けて考えることで、$\lbrack N \rbrack$ の分割への帰着を試みましょう。

$$ \hat f _ { N + 1 } = \sum _ { \mathcal A \vdash \lbrack N \rbrack \sqcup \lbrace \star \rbrace } \prod _ { A \in \mathcal A } f _ { \lvert A \rvert } = \sum _ { S \subseteq \lbrack N \rbrack } f _ { N + 1 - \lvert S \rvert } \sum _ { \mathcal A \vdash \lbrack N \rbrack } \prod _ { A \in \mathcal A } f _ { \lvert A \rvert } = \sum _ { k = 0 } ^ N \binom N k f _ { N + 1 - k } \hat f _ k $$

あらあら、コンボリューションですね。コンボリューションは指数型母関数に移すと形式的べき級数の積です。また添字のシフトは微分でしたね。いうことは、次の微分方程式が成り立つことがわかります。

$$ \frac { \mathrm d } { \mathrm d x } \hat f ( x ) = \hat f ( x ) \frac d { dx } f ( x ) $$

さらに初期値 $\hat f ( 0 ) = 1$ より、よく知られているように $\hat f ( x ) = \exp f ( x )$ が唯一の解となるわけです。(なお $f$ は定数項を持たなかったことに注意です。)

ちなみに先程導出した漸化式に $f _ j = 1 \ ( j \in \mathbb N _ +)$ を代入すると、ベル数の有名な漸化式 $B _ { N + 1 } = \sum _ { j = 0 } ^ N \binom N j B _ j$(🔗Bell_number - Wikipedia#Summation_formulas)になることもわかり、ひと安心なわけです。もちろん母関数(🔗Bell_number - Wikipedia#Generating_function)の方も大丈夫です。

計算方法2:すんごいがんばる

実は頑張ると頑張れます。押忍。次のようなステップで変形していきます。

  1. 集合分割 $\mathcal A \vdash \bracked N$ に関する和を、自然数の分割 $\lambda \vdash N$ に関する和に変形します。このとき $N! / \left ( \prod _ { j = 1} ^ { \infty } m _ j ! { j ! } ^ { m _ j } \right )$(ただし $m _ j$ は $\lambda$ の要素のうち $j$ であるものの個数です。)個の項を纏めることになるため、これが係数としてかかります。
  2. 分割の長さ $l$ により、和を分解します。
  3. それを今度は分割とは限らない数列 $a \in \mathbb N _ + ^ l$ の和に分解します。これにより一つの項が $l ! / \left ( \prod _ { i = 1 } ^ l { a _ i ! } \right )$ 個に分かれるため、この逆数が係数としてかかります。

結局この変形により、係数 $\frac { N ! } { l ! } \cdot \prod _ { i = 1 } ^ l \frac 1 { a _ i !}$ がかかることがわかりますから、このようになります。(しれっとやっていますが、相当複雑で間違えやすい計算ですから、みなさまも何も見ずにぜひです。)

$$ \hat f ( x ) = \sum _ { N = 0 } ^ { \infty } \frac 1 { N ! } \sum _ { \mathcal A \vdash \bracked N } \prod _ { A \in \mathcal A } \left ( f _ { \lvert A \rvert } x ^ { \lvert A \rvert } \right ) = \sum _ { l = 0 } ^ { \infty } \frac 1 { l ! } \sum _ { a \in \mathbb N _ + ^ l } \prod _ { j = 1 } ^ l f _ { a _ i } \frac { x ^ { a _ i } } { a _ i ! } = \exp f ( x ) $$

ちなみに大学院生の頃の私はこの手の計算が微分方程式でできることに気づかず、また典型を典型として考えることもしなかったため、似たような地獄計算をなんどもしていたのでした。悲しいですね。けっこう掛かるんですよ?これ(泣)

応用例

応用例1:置換の総数

ところで皆様、$N$ 元集合 $\bracked N$ の置換が全部でいくつあるかご存知でしょうか。ご存知ありませんよね(圧)。しかしなにも心配することはありません。私たちには指数型母関数の exp がついています。まずは置換をサイクルに分解しましょう。

サイクルへの分解が $\bracked N$ の分割 $\mathcal A \vdash \bracked N$ を定めますが、逆に分割 $\mathcal A \vdash \bracked N$ に対応する置換はいくつあるでしょうか? ええ、そのとおりです。分割成分 $A$ ごとに円順列 $(A - 1)!$ ですから、$f _ j = ( j - 1) !$ となり、$f ( x ) = \sum _ { j = 1 } ^ \infty \frac 1 j x ^ j = \frac d { dx } \frac 1 { 1 - x }$ ですね。従って $\hat f ( x ) = \exp f ( x ) = \frac 1 { 1 - x }$ ですから、$\hat f _ N = N!$ がわかるわけです。ええ、今後はこの方法で導出していただいて。

応用例2:ラベル付き連結単純グラフの総数

頂点数 $N$ (ただし、$N \ge 1$)のラベル付き連結単純グラフの総数を計算しましょう。今度は逆に考えます。求めたい個数の指数型母関数を $f ( x )$ と置くと、$\exp f ( x )$ は連結とは限らない単純グラフの総数の指数型母関数になりますから、

$$ f ( x ) = \log \sum _ { i = 0 } ^ { \infty } 2 ^ { \binom i 2 } \frac { x ^ i } { i ! } $$

となります。

余談ですがこれは分割束のメビウス反転でも計算することができます。連結とは限らない単純グラフのうち、連結成分分解が $\mathcal A \vdash \bracked N$ になるものの個数を $a _ { \mathcal A }$ とおきますが、これはそのままではムズカシソウです。そこで条件を緩和して連結成分分解が $\mathcal A \vdash \bracked N$ と同じかそれより細かいものの個数を考えると、それは $\prod _ { A \in \mathcal A } 2 ^ { \binom { \lvert A \rvert } 2 }$ となりますから、メビウスの反転公式より、連結なものの個数は、

$$ a _ { \top } = \sum _ { \mathcal A \vdash \bracked N } \mu ( \mathcal A, \top ) \prod _ { A \in \mathcal A } 2 ^ { \binom { \lvert A \rvert } 2 } = -\sum _ { \mathcal A \vdash \bracked N } \prod _ { A \in \mathcal A } - \left ( \lvert A \rvert - 1 \right ) ! \cdot2 ^ { \binom { \lvert A \rvert } 2 } $$

(ただし $\top$ は分割束の最大元 $\braced { \bracked N }$、 $\mu ( \mathcal A, \top )$ はメビウス関数の値 $(-1) ^ { \lvert \mathcal A \rvert - 1 } \prod _ { A \in \mathcal A } \left ( \lvert A \rvert - 1 \right ) !$ です。)とあらわされます。これの指数型母関数 $\hat f ( x )$ は、$f _ j = - ( j - 1 ) ! \cdot 2 ^ { \binom j 2 }$ の指数型母関数の exp ですから、

$$ \hat f ( x ) = \exp \left ( - \sum _ { j = 1 } ^ N - ( j - 1 ) ! \cdot 2 ^ { \binom j 2 } \frac { x ^ j } { j ! } \right ) $$

とあらわせることがわかります。

ちなみに計算ちょっと自信なしです。紙やコンピュータで検算する気力が残っていませんでした。(あのですね。)

Further reading

まとめ

結局指数型母関数の exp についておわかりいただけましたでしょうか。やわらかめな自然言語で(わかっていてかつ偶々私の雑目なご説明が嵌まる方向けに)ご説明すると結局、何らかの数え上げ $( f _ j ) _ { j = 0 } ^ { \infty }$ がわかっているとき、有限集合に対してそれを集合分割してその中で(空成分がない分1個添字をずらして) $f$ で数えるような数え上げ $( \hat f _ j ) _ { j = 0 } ^ { \infty }$ は、指数型母関数で言うともとの $f$ の exp になっているというわけです。

競技プログラミングわりと時々出る印象なのですが、探すと見つからないわけでしてですね。むぅ……申し訳ない気持ちです。問題例募集中です。

タグをつける

ベル数

指数型母関数

形式的べき級数

6182文字