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

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

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

解説 FFT NTT 形式的べき級数 数え上げ スターリング数 分割数 包除原理 ベル数 重複組み合わせ 数学

先日、競プロやってたらhotmanから「形式的べき級数と数え上げの相性が抜群すぎてつながってて気持ちいい、世の中の眠る真理が目覚めた気がする」といわれて、気になったのでまとめた。
この記事は、数学的厳密性に欠けています。多くの変形が厳密な確認をなしにこれはこうと怪しいものが見受けられますが、初心者の人にお気持ちが伝わればいいと思います。ごめんなさい。
また、この記事は数え上げとべき級数はこんな感じでつながってるんだーと伝えるもので、有益テクがかなり含まれてるなどというわけでもありませんのでご注意ください。

この記事を書くにあたって、ずっと討論を重ねてくれたhotman(@hotmanww)さん、写像12相をすごくわかりやすい記事にまとめてくれたけんちょんさん(@drken1215)とTwitterで疑問を氷解させてくれた熨斗さん(@noshi91)と.さん(@___n___z)に多大なる敬意を表します。

写像12相とは？

けんちょん先生の次の記事を閲覧するとわかります。

qiita.com

この中に書かれてる、数え上げの問題に関して2*2*3=12通りの条件で場合分けをして、それぞれの条件下での数え上げをする方法をまとめたものです。体系的に数え上げの各種の考え方を網羅してるもので有名です。
ちなみに、本記事では写像12相についての詳しい解説をするわけではないので、上記の記事を同時に開いて閲覧することを勧めます。

次が写像12相の一覧です。そのうちのほとんどを今回と次回でやります。

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

形式的べき級数とは？

有限の長さ nの数列、 a_nを考えます。たとえば、長さ3の数列 a_0 = 1, a_1 = 1, a_2 = 4などがあります。
この数列の a_iが x_iの係数となるような多項式を考えてみます。先ほどの例だと、 a_0x^0+a_1x^1+a_2+x^2=1+1x+4x^2ですね。これを、数列 \{a_n\}の(通常型)母関数(ぼかんすう)と言います。通常型以外にも色々ありまして、その内、今回の記事で出てくる予定なのは指数型母関数です。

ここで、無限の長さを持つ数列の(通常型)母関数について考えてみることにします。すなわち、
無限数列 \{a_n\}に対して、 \sum_{i=0}^{\infty}a_ix^iを考えます。

ちなみに、無限に続く多項式は、べき級数と言います。 1+x+x^2+x^3+...のようなものです。

数学では、無限を考えると慎重にならないといけません。有限で成り立つと思われる当然のことが、無限では成り立たなくても不思議ではないです。この記事はそんなことを思いっきり無視するので数学的厳密性がガバガバです。

ひとまず、有限数列で考えた(通常型)母関数があったのですから、無限数列にも(通常型)母関数という概念を導入しようと考えるとき、その(通常型)母関数は無限の長さのべき級数になります。実はこれは、加減乗除において、普通の有限の長さのべき級数とも同じ扱いができる！ので、このような母関数の書き方をひとまず認めて、それに名前を与えます。その名前こそが、「形式的べき級数」です。
実を言うと、形式的べき級数という無限に続く多項式を認めて、それの x^n係数を数列の項 a_nとして定めたのが、数列 \{a_n\}に対して定めた(通常型)母関数です。

写像12相とべき級数の関係性

形式的べき級数と数え上げの関連性を解き明かします。形式的べき級数での表現方法のルールは、表現したいものが増えるにつれて、どんどんその都度追加します。

また、写像12相での2つの0 or 1のマスですが、今回はイレギュラーということもあり割愛します。

玉を区別しない　箱を区別する　個数は0~1個

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

区別しない n個の玉を区別する k個の箱に対して、それぞれ入れるor入れないをするときの場合の数です。
( k >= n)これを写像12相では、 {}_k C _nのマスになってます。これを形式的べき級数から導いてみます。

ひとまず、次の式ついて着目してください。
(1x^0+1x^1)^n = (1+x)^k
これを、このように意味付けします。
1つの箱についての操作は、玉を1ついれるかいれないかの二択である。玉を i個入れる場合の数はtex: x^i]にかかる係数とする。 (1+x)は1つの箱についての選択であり、これらを k回行う、つまり掛け合わせると上の式になる。

ルール
  • 玉を i個入れる場合の数は x^iにかかる係数とする。 <- New!
  • 掛け合わせる多項式のうちの一つのユニットは、上のルールにのっとり可能な選択肢を意味する x^iをいくつか集めた和とする。<- New!

上の式での x^nの係数は、 {}_k C _nであることは、二項定理で展開することで正しいことが把握できますね。

玉を区別しない　箱を区別する　個数は無制限

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

区別しない n個の玉を区別する k個の箱に対して、それぞれ任意にいれたときの場合の数です。
これは、先ほどの考え方と似てます。さきほどは1つの箱に0~1個しか許容しないがゆえに、 (1+x)を k乗することになってました。しかし、今回では無制限個使用可能なので、 (1+x+x^2+x^3+...)のような形式的べき級数を k乗すると考えられます。

ルール
  • 玉を i個入れる場合の数は x^iにかかる係数とする。
  • 掛け合わせる多項式のうちの一つのユニットは、上のルールにのっとり可能な選択肢を意味する x^iをいくつか集めた和とする。その結果、ユニットごとに形式的べき級数となってもよい。 <- New!

これを計算すると、 {}_{n+k-1} C _nになります。具体的な計算方法は、重複組み合わせとみなせばいいです。(投げやり)次のページの「分割数と形式的べき級数」の章の最後らへんに書かれてます。
maspypy.com

玉を区別する　箱を区別する　個数は無制限

区別する n個の玉を区別する k個の箱に対して、それぞれ任意にいれたときの場合の数です。12相では、 k^nになってます。

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

このように、玉を区別するとどう書けばいいのでしょう？ヒントは、「同じものを含む順列」です。同じものを含む順列では、全部合計 p個のうち、Aが a個、Bが b個、Cが c個...などの時、それの場合の数は \frac{p!}{a!b!c!...}になります。この問題では、次のように考えます。
ある箱で a個選び、また別の箱で b個選ぶ...ということは、上の式のように重複組み合わせと考えられる。
これを式にすると
(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)を1ユニットとして、最後に n!を掛ければよい。すなわち、
n!(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^kの x^nの項の係数となる。

この式を高速フーリエ変換、繰り返し二乗法を利用して計算すると、計算量が O(k \log^2(k))となり、到底効率的なものではないです。この式からさらに変形を重ねて、はっきりとわかる形にすることができます。

ところで、みなさん、この式に見おぼえありませんか？

1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...

これはどう見ても、 e^xのマクローリン展開ですね（真理開眼）。この変形ができることが非常に大事です。

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

この新ルールを使って、さきほどの k乗の式を書き換えてみる。

n!(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^k = n!(e^x)^k = n!e^{(kx)} = n!(1+\frac{kx}{1!}+\frac{kx^2}{2!}+\frac{kx^3}{3!}+...)
となります。これの x^nの係数は、 n!\frac{k^n}{n!}=k^nであり、写像12相の導き出したものと一致しますね。

玉を区別する　箱を区別する　個数は0~1個

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

区別する n個の玉を区別する k個の箱に対して、箱に最大1つ入れたときの場合の数です。
( k >= n)12相では、 k^nになってます。これは先ほどの例のように、重複組み合わせとみなして考えると(今回の場合は、箱にたかだか1つしか入らないので、実質的に n!を掛けるだけである)、
n!(1+\frac{x}{1!})^kになります。
二項係数により x^nの係数は n!{}_k C _nとなり、これは
n!{}_k C _n = \frac{n!k!}{n!(k-n)!}= \frac{k!}{(k-n)!}= {} _k P _n
となり、写像12相の結果とも一致しますね。

玉を区別する　箱を区別する　個数は1個以上

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

区別する n個の玉を区別する k個の箱に対して、箱に最低1つ入れたときの場合の数です。けんちょんさんの記事ではラスボス扱いです。
まず、個数が1つ以上という条件を形式的べき級数に直すと、
x+x^2+x^3+...となります。
さらに、区別するという情報を盛り込んだ場合、
\frac{x}{1!}+\frac{x}{2!}+\frac{x}{3!}+...となり、これはルールの3つ目から、 e^x-1と書けます。これをベースに考えます。
以上のことを定式化すると、 n!(e^x-1)^kの x^nの係数になります。この式から n!を無視して、変形していきます。 n!は最後につけます。
(e^x-1)^kを (a+b)^c(ただし、 a=e^x, b=-1, c=kとみなして)と考えて、二項定理を適用させます。すると、
{} _n C _0 (e^x)^k-{} _n C _1 (e^x)^{(k-1)}+{} _n C _2 (e^x)^{(k-2)}+...と展開できます。
この時、 e^{ax}をべき級数の形に展開すると、 x^nの項の係数は \frac{a^n}{n!}となることから、全部の e^xの形をしたものを展開すると係数は、
{} _n C _0 \frac{k^n}{n!}-{} _n C _1 \frac{(k-1)^n}{n!}+ {}_n C _2 \frac{(k-2)^n}{n!}-...
= {} _n C _k \frac{k^n}{n!}-{} _n C _{k-1} \frac{(k-1)^n}{n!}+ {}_n C _{k-2} \frac{(k-2)^n}{n!}-... ( {}_a C_ b = {}_a C_{a-b}であることを利用して、コンビネーションの中身を入れ替えた。)
= \frac{\sum_{i=0}^{k} (-1)^{k-i}{} _k C _i i^n}{n!}
となります。最後に n!を掛けることを考えると、これも写像12相の包除原理で考えたのと同じ結果となっていますね。形式的べき級数すごい。

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

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

区別しない n個の玉を区別する k個の箱に対して、箱に最低1つ入れたときの場合の数です。個数無制限のものと似ています。
形式的べき級数で書くと、 (x+x^2+...)^kの x^nの係数です。
(x+x^2+...)^k=x^k(1+x+x^2+...)^kとなり、これは実質的に「玉を区別しない　箱を区別する　個数は任意」ののと同じですね。よって、受験数学からでもよくあるように、あらかじめすべての箱に1つの玉を入れて、計 n-k個の玉を入れる重複組み合わせと考えられます。これも写像12相の結果(ついでに言うと考え方も)一致しています。

最後に

ここまで計8個を紹介して、残った4つはいずれも難易度が高いため、記事の後編で書きます。(できるだけ早く書き上げます)こうご期待！
最後に、現時点でのルールを載せます（おそらくこれ以上追加されることも多分ありませんが・・・）

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