LoginSignup
5
0

More than 3 years have passed since last update.

分割関連の数え上げはとりあえず指数型母関数にすると exp にまとまりがちですのご紹介です。

Last updated at Posted at 2021-04-29

たとえば、次のものの指数型母関数がわかります。(他にも思い出したらあとから加筆していくかんじで行きます。みなさまもご提案ぜひです!)

  • ベル数 $B _ n$(要素数 $n$ の集合 $[n]$ の分割の個数)

こちらの公式を使うと良いです。

$R$ を可換環、$x$ を不定元、$f: \mathbb N _ + \rightarrow R$ を関数として、

$$
\sum _ { n \ge 0 } \left ( \sum _ { \mathcal A \vdash [ n ] } \prod _ { A \in \mathcal A } f ( \vert A \vert ) \right ) \frac { x ^ n } { n ! }
= \exp \left ( \sum _ { j \ge 1 } f ( j ) \frac { x ^ j } { j ! } \right )
$$

が成り立ちます。

証明

集合 $[n]$ の分割 $\mathcal A$ に対して、その要素数を降順に並べてできる自然数 $n$ の分割 $\lambda$ を対応させます。$\lambda _ i = j$ となる $i$ の個数を $m _ j$ と置くことにすると、この対応は、置換群 $\mathfrak S _ n$ の $[n]$ への作用の $\mathcal A$ における固定化部分群を考えると、$n ! / { \prod _ { j \ge 1 } j ! ^ { m _ j } m _ j ! }$ 対 $1$ 写像であることがわかります。

さらに、有限な長さ $l$ を持つ正整数列 $a \in \mathbb N _ + ^ l$ に対して、それを降順ソートしてできる自然数 $n$ の分割 $\lambda$ を対応させます。この対応は、置換群 $\mathfrak S _ l$ の $\mathbb N _ + ^ l$ への作用の $a$ における固定化部分群を考えると、$l ! / { \prod _ { j \ge 1 } m _ j ! }$ 対 $1$ 写像であることがわかります。

これにより $\mathcal A$ 添字な和を $a$ 添字な和にまとめ直すと、これは $n ! / { l ! \prod _ { j \ge 1 } j ! ^ { m _ j } }$ 対 $1$ 対応になります。すなわち、

$$
( \mathrm { LHS } )
= \sum _ { l \ge 0 } \frac 1 { l ! } \sum _ { a \in \mathbb N _ + ^ l } \prod _ { j \ge 1 } \frac { f ( j ) x ^ j } { j ! }
$$

となります。これを因数分解して $\exp$ でまとめると、右辺に等しくなります。

ベル数

公式に $f ( j ) = 1 \ ( j \ge 1 )$ を代入すると良いです。すると、ベル数の指数型母関数はつぎのようになります。

$$
\sum _ { n \ge 0 } B _ n \frac { x ^ n } { n ! }
= \exp \left ( \sum _ { j \ge 1 } \frac { x ^ j } { j ! } \right )
= e ^ { e ^ x - 1 }
$$

Wikipedia - ベル数 をご覧いただくと、この結果も書いてあります。

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
0