(形式的)べき級数と数え上げの写像12相との関係性　後編

前編の読了お疲れさまでした。形式的べき級数でいくつかの数え上げを解決して、残るは数え上げの難関の3つの数(僕呼び)の、スターリング数、ベル数、分割数のみです。この三つの数はいずれも一般的な場合では漸化式を使わない式で表せません。今回の記事では、これらの効率的な計算法は出てきませんが、数学的な変形の果てに眠り真理を見て感動したい予定でいきます。

参考資料として、けんちょんさん作の写像12相に対する解説を読むことを勧めます。表や解説が分かりやすいため、今回も同時に見ながら理解を深めてほしいです。
qiita.com

では、始める前に現時点での形式的べき級数のルールを確認しましょう。

ルール

玉を $i$ 個入れる場合の数は $x^i$ にかかる係数とする。
掛け合わせる多項式のうちの一つのユニットは、上のルールにのっとり可能な選択肢を意味する $x^i$ をいくつか集めた和とする。その結果、ユニットごとに形式的べき級数となってもよい。
1つの箱について、無制限個選択可能の時を表す $1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...$ はマクローリン展開とみなして、 $e^x$ として扱ってよい。

＜表＞

		箱に0~1個	箱に無制限	箱に1個以上
箱を区別する	玉を区別する	前回	前回	前回
箱を区別する	玉を区別しない	前回	前回	前回
箱を区別しない	玉を区別する	省略	今回	今回
箱を区別しない	玉を区別しない	省略	今回	今回

この表の右下の4つのマスは、一般的に漸化式なしでは項を表せないラスボスのようなマスです。この記事の後編はこの4つのマスの解説、そして少しばかりの例題を紹介しようと思います。

箱を区別しない　玉を区別する　箱に1個以上

		箱に0~1個	箱に無制限	箱に1個以上
箱を区別する	玉を区別する	前回	前回	前回
箱を区別する	玉を区別しない	前回	前回	前回
箱を区別しない	玉を区別する	省略	今回	Now!
箱を区別しない	玉を区別しない	省略	今回	今回

区別しない箱k個に、お互いに区別する玉n個を、最低箱に1つ入れる場合の場合の数です。

この場合、実は前編の、「箱を区別する　玉を区別する　箱に1個以上」と非常に似てます。なぜならば、箱に1つ以上必ず玉があるので、確実に1個以上入ってる箱はちょうどk個あります。(それはそう)
ここで、何かが入ってる箱と何もない箱についての玉を区別する際の重要な違いについて説明します。玉を区別する際、箱を区別しなくするにあたって、すべての箱に貼ってある番号のラベルを取るとイメージすれば、 $k!$ で割ればよいしかし、何も入ってない箱が存在してる場合、それらがi個存在してる場合、そのi個のもの同士は区別がつかないので、 $(k-i)!$ で割ることになります。
今回の場合、すべての箱には必ず1つは入ってるので、 $k!$ で割れば答えが求まる。これは、写像12相のほかのマスでは適応できない操作といえる。玉を区別しながら箱の区別をなくすのはこれだけであるので。

「箱を区別する　玉を区別する　箱に1個以上」は、形式的べき級数では
${(e^x-1)^k}$ の $x^n$ の項の係数なので $\sum_{i=0}^{k} (-1)^i _k C _i i^n$ である。これに $\frac{1}{k!}$ を乗じて、答えは $\frac{1}{k!}\sum_{i=0}^{k} (-1)^i _k C _i i^n$ となる。

箱を区別しない　玉を区別する　箱に制限なし

		箱に0~1個	箱に無制限	箱に1個以上
箱を区別する	玉を区別する	前回	前回	前回
箱を区別する	玉を区別しない	前回	前回	前回
箱を区別しない	玉を区別する	省略	Now!	今回
箱を区別しない	玉を区別しない	省略	今回	今回

区別しない箱k個に、お互いに区別する玉n個を、箱に何個入れてもいい場合の場合の数です。

これはベル数という有名な組み合わせの数で、一部の場合を除き漸化式でしか表せません。 $n=k$ に限り、以下の公式で表せますが、求めるの計算量から、非現実的なものです。けんちょんさんの記事にある漸化式を解いたほうがいいです。ちなみにこの式の導出では、今までの標準的なべき級数方の母関数とは異なり、指数型の母関数とみなしています。後程の式変形をさらに極めると出てきます。気になる方は次のPDFをご覧ください。

$\frac{1}{e}(1+\frac{2^n}{1!}+\frac{3^n}{2!}+\frac{4^n}{3!}+...)$

http://izumi-math.jp/I_Yanagita/bellnumber.pdf

さて、けんちょんさんの記事のとおりに、スターリング数からベル数を求めると、
$\sum_ {i=0}^{k} \frac{(e^x-1)^i}{i!}$ の $x^n$ の係数になる。新ルールの追加もなくここらへんは淡々としていてなにもないです。

ですが、面白い点を紹介します。上の式、 $e^x$ のマクローリン展開と非常に似てますよね。上の式の $k=n, {n \to \infty}$ とするとき、
$e^{e^x-1}$ になります。これは、「区別しない箱n個に、お互いに区別する玉n個を、箱に何個入れてもいい場合の場合の数」の[tex: n:が∞に飛ぶ際の母関数となります。

箱を区別しない　玉を区別しない　箱に無制限 or 1個以上

		箱に0~1個	箱に無制限	箱に1個以上
箱を区別する	玉を区別する	前回	前回	前回
箱を区別する	玉を区別しない	前回	前回	前回
箱を区別しない	玉を区別する	省略	今回	今回
箱を区別しない	玉を区別しない	省略	Now!	Now!

区別しない箱k個に、お互いに区別しない玉n個を、箱に何個入れてもいい場合 or 1個以上固定の場合の場合の数です。

1個以上固定の場合、すべての箱にあらかじめ1つずつ箱を入れれば、箱に何個入れてもいいものに帰着可能です。

これはおそらく、 $n$ 個の玉を $k$ 個の箱に入れるということ、つまり、 $k$ と $n$ をうまく絡めた形式的べき級数で表す方法はありません。
WikiPediaさんによりますと、分割数の母関数は
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...(1+x^k)$ となり、その $x^n$ の係数が答えとなります。これは $n$ 個の玉を任意個の箱に入れるときの場合の数です。(Wikipediaやほかのサイトではこれを分割数と言ってるものが多いです。本来は $n$ と $k$ の二変数関数だが、任意個の箱に分けることから $k$ が変数でなくなってる)
ちなみに、1個以上入れる場合は、すべての掛け合わせてる項の1を除いて簡単な式変形をすることによって、簡単に個数制限なしの場合に帰着できるとわかります。

上の式を変形させてみます。
$1+t^k+t^{2k}+t^{3k}+...=\frac{1}{1-t^k}$
が成立するため、(等比数列の和の式 $1+x+x^2+...=\frac{1}{1-x}$ の $x$ に $x=t^k$ として変数置換するとわかる。)
これで上の式を書き直すと、
$\prod_{k=1}^{\infty} \frac{1}{1-x^k}$
にすることができます。
これでは式が見やすくなりましたが、まだ計算できるものではありません。
そこで、オイラーの五角数定理という定理を使います。
この定理はつぎのようなものを満たします。
$\prod_{k=1}^{\infty} (1-x^k)= \sum_{k=-\infty}^{\infty}{(-1)^k x^{\frac{k(3k+1)}{2}}}= 1+\sum_{k=1}^{\infty}{(-1)^k (x^{\frac{k(3k+1)}{2}}+x^{\frac{k(3k-1)}{2}})}$

これの左辺はちょうど先ほどの式の逆数であるので、がんばってFFTすることで、 $x^n$ の係数であり、 $O(log n)$ でn個の玉を任意個の箱に入れる場合の数を求められます。
ちなみに、これはピンポイントで求める場合であり、普通に分割数がほしいのならば、やはりけんちょんさんの記事のとおりに $O(NK)$ で計算することを勧めます。

例題

最後に、形式的べき級数を少し使う問題を紹介します。

6面サイコロをN(<= 10^5)回振り、それの和がS(<= 10^5)になる場合の数を求めよ。

開始早々ですが、この問題おそらく動的計画法の方が簡単に思い浮かび、そしてその遷移の式は7項間漸化式なので蟻本のとおりに行列累乗することでとけます。しかし、あえて形式的べき級数で考えてみます。

この問題を形式的べき級数で立式してみます。

$(x^1+x^2+x^3+...+x^6)^N$ の $x^S$ の係数となります。

ここで、愚直に繰り返し二乗法とFFTを用いて計算すると、計算量は $O(S \log {N})$ となり、時間内に間に合います。このような殴る操作が可能です。

最後に

形式的べき級数について、がっつり勉強したものを纏めました。素晴らしさが伝われば幸いです。最後に、これの成立にかかわった多くの方への感謝の意を述べて終わりにしたいと思います。

Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど