場合の数問題を多項式で瞬殺する

皆様ごきげんよう。
突然ですが、まずはこちらの問題をご覧ください。よければ少し考えてみてください。

1　展開は「選択」の記録

まずは、よく知っている式から始めましょう。
$$ (1+x)^n=\underbrace{(1+x)(1+x)\cdots(1+x)}_{n\text{個}} $$
この積を展開するときは、各括弧から$1$または$x$を一つずつ選び、それらを掛けます。
$x^k$を作るには、ちょうど$k$個の括弧から$x$を選べばよい。その選び方は${}_nC_k$通りなので、$x^k$の係数は${}_nC_k$です。これが
$$ (1+x)^n=\sum_{k=0}^{n}{}_nC_kx^k $$
という二項定理の、場合の数としての意味でした。

カードの何を記録すればよいか

冒頭の問題では、積そのものを計算しなくても、素因数$2,3$の指数が分かれば平方数かどうかを判定できます。
そこで、$2$の指数を$x$の指数に、$3$の指数を$y$の指数に記録します。

$1$も一つの選択肢です。指数を増やさない選択なので、$0$ではなく$x^0y^0=1$で記録します。
一回の選択では、これら四つのうちどれか一つを選びます。その選択肢を、括弧の中に
$$ 1+x+y+x^2 $$
と並べておきます。ここでの足し算は、四枚を同時に選ぶという意味ではありません。展開するときに選べる項を、一つの括弧に用意しているのです。
三回の選択なら、括弧を三つ用意します。
$$ \begin{aligned} &(1+x+y+x^2)(1+x+y+x^2)\\ &\qquad{}\times(1+x+y+x^2) \end{aligned} $$
第一の括弧から選ぶ項は一回目のカード、第二は二回目、第三は三回目に対応します。分配法則で展開すると、各括弧から一項ずつ選ぶすべての組合せが、一度ずつ現れます。
例えば、カードを$2,4,3$の順に選んだ場合、対応する項は
$$ x\cdot x^2\cdot y=x^3y $$
です。一方、カードの積も$2\cdot4\cdot3=2^3 3^1$。$x,y$の指数が、素因数$2,3$の指数をそのまま記録しています。
カードの数を掛けると素因数の指数が足され、単項式を掛けても文字の指数が足される。この対応があるので、複数回の選択を積で表せるわけです。
同様に$n$回なら、一回につき一つ、合計$n$個の括弧を用意して
$$ F(x,y)=(1+x+y+x^2)^n $$
となります。$x,y$は、今の段階では値を求める未知数というより、情報を記録するための記号だと思ってください。

同じ記録がまとまると、係数になる

例えば二回の選択で積が$4$になるのは、順序を区別して
$$ (1,4),\quad(2,2),\quad(4,1) $$
の三通りです。展開では、それぞれ$1\cdot x^2$、$x\cdot x$、$x^2\cdot1$を生みます。まとめると$3x^2$となり、係数$3$に三通り分の情報が残ります。
一般にも、まとめる前の各項は一つの選択列に対応し、その係数は$1$です。同じ$x^ay^b$を生む項を足し合わせれば、係数はその選択列の個数になります。

2　代入で取り出し、冒頭の問題を解く

1と−1で、偶数次だけを拾う

まず、一変数の有限多項式
$$ P(x)=a_0+a_1x+a_2x^2+\cdots+a_Nx^N $$
を考えます。$x=1$を代入すると、すべての$x^k$が$1$になるので、$P(1)$は係数全体の和です。
一方、$x=-1$なら、偶数次の項はそのまま、奇数次の項は符号が反転します。偶数次の係数和を$E$、奇数次の係数和を$O$とおけば、
$$ P(1)=E+O,\qquad P(-1)=E-O. $$
足し算と引き算から、次の二式が得られます。

二つの条件は、一つずつ処理する

冒頭の$F(x,y)$へ戻りましょう。平方数となる条件は、$x$の指数も$y$の指数も偶数であることでした。
まずは$y$をそのままにして、$x$についてだけ操作します。
$$ H(y)=\frac{F(1,y)+F(-1,y)}2 $$
例えば、元の項が$c x^a y^b$なら、この操作による寄与は
$$ c\,\frac{1+(-1)^a}{2}\,y^b $$
です。$a$が奇数なら$0$、偶数なら$c y^b$になります。つまり、$x$の指数が偶数である場合だけが残り、$y$の指数の情報はまだ保たれています。
次に、$H(y)$から$y$の偶数次の係数和を取り出します。求める個数を$N_n$とすると、
$$ N_n=\frac{H(1)+H(-1)}2. $$
$H$の式を戻せば、
$$ \begin{aligned} N_n=\frac14\bigl\{&F(1,1)+F(-1,1)\\ &+F(1,-1)+F(-1,-1)\bigr\} \end{aligned} $$
です。冒頭の四つの代入は、偶数次を取り出す操作を、二つの変数に一回ずつ行ったものでした。
あとは代入するだけです。

$n\geq1$なので、最後の値は$0$です。したがって
$$ N_n=\frac{4^n+2^{n+1}}4=4^{n-1}+2^{n-1}. $$

3　次の問題では、何を記録するか

別の問題で使うには、「あの多項式」を覚えるより、何を指数に記録すると、最後の条件を読み取れるかを考えることが大切です。
今回、変数が二つだったのは、平方数判定のために素因数$2,3$の指数を別々に追跡する必要があったからです。$5$の指数も必要なら、
$$ 2^a3^b5^c\longleftrightarrow x^ay^bz^c $$
とすればよい。同じように、選んだ枚数と数の和など、性質の違う情報も同時に記録できます。

積ではなく、和を調べる問題でも

次の問題では、何を記録すればよいでしょうか。解答を開く前に、一枚のカードに対応する括弧を考えてみてください。

発展　偶奇から一般の合同条件へ

まず、指数が3の倍数の項を取り出す

$1,-1$は、どちらも二乗すると$1$になる数でした。では、三乗すると$1$になる数を使えばどうでしょうか。
$z^3=1$を解くと、
$$ 1,\quad\frac{-1+\sqrt3\,i}{2},\quad\frac{-1-\sqrt3\,i}{2} $$
の三つです。二番目の数を$u$と書くことにすると、三番目は$u^2$であり、
$$ u^3=1,\qquad 1+u+u^2=0 $$
が成り立ちます。
ここで、$P(1)+P(u)+P(u^2)$を考えます。元の$a_kx^k$という項は、足し合わせると$a_k(1+u^k+u^{2k})$を生みます。

したがって、三つの値を足して$3$で割れば、指数が$3$の倍数の項の係数だけが残ります。
$$ \frac{P(1)+P(u)+P(u^2)}3=a_0+a_3+a_6+\cdots $$
右辺は、$P$の次数以下の項までの有限和です。例えば$P(x)=1+2x+3x^2+4x^3+5x^4$なら、この値は$1+4=5$となります。

一般のmでも、仕組みは等比数列

$m$を$2$以上の整数とし、
$$ q=\cos\frac{2\pi}{m}+i\sin\frac{2\pi}{m} $$
とおきます。ド・モアブルの定理より、$z^m=1$の$m$個の解は
$$ 1,q,q^2,\ldots,q^{m-1} $$
です。$q$は一回掛けるごとに角度$2\pi/m$だけ回る数で、$q^d=1$となるのは整数$d$が$m$の倍数のときに限ります。
整数$d$について、次の和を調べましょう。
$$ 1+q^d+q^{2d}+\cdots+q^{(m-1)d} $$
$d$が$m$の倍数なら、各項が$1$なので和は$m$。そうでなければ、公比$q^d\ne1$の等比数列の和として
$$ \frac{1-(q^d)^m}{1-q^d}=0 $$
となります。分子が$0$なのは、$(q^d)^m=(q^m)^d=1$だからです。負の$d$についても同じ議論が成り立ちます。
一項$a_kx^k$にこの仕組みを使うと、$m$の倍数の次数だけが残るので、有限多項式$P(x)=\sum_{k=0}^{N}a_kx^k$について、
$$ \frac1m\sum_{j=0}^{m-1}P(q^j) =\sum_{\substack{0\leq k\leq N\\k\equiv0\pmod m}}a_k $$
が得られます。右辺は、「$0\leq k\leq N$のうち、$k$が$m$の倍数であるものだけで足す」という意味です。

余りがrとなる項も取り出せる

例えば$3$で割って$1$余る次数を取り出したいなら、
$$ \frac{P(1)+u^{-1}P(u)+u^{-2}P(u^2)}3 $$
とします。元の$a_kx^k$に掛かる数が、今度は$\{1+u^{k-1}+u^{2(k-1)}\}/3$となるため、$k-1$が$3$の倍数のときだけ残ります。なお、$u^{-1}=u^2$、$u^{-2}=u$です。
一般にも、$0\leq r< m$を満たす整数$r$について、代入値ごとに$q^{-jr}$を掛ければ、指数の判定が$k$から$k-r$へずれます。

平方数から、立方数・一般のm乗数へ

正の整数が$m$乗数となる条件は、素因数分解に現れる指数がすべて$m$の倍数であることです。各指数が$m$の倍数なら$m$乗を括り出せ、逆に$m$乗した整数の各指数は$m$の倍数になります。

冒頭と同じ$F(x,y)=(1+x+y+x^2)^n$を使えば、$X_n$が$m$乗数となる確率は
$$ \boxed{\frac{1}{m^2 4^n}\sum_{j=0}^{m-1}\sum_{k=0}^{m-1}\bigl(1+q^j+q^k+q^{2j}\bigr)^n} $$
と表せます。$x$の指数に一回、$y$の指数に一回フィルターを掛けるので、$m$で二回割ります。その後、全選択列の個数$4^n$で割っています。
$m=2$なら本編の四つの代入、$m=3$なら九つの代入です。変数が三つ必要なら、三つ目にも同じ操作を加えます。各変数に違う条件を課すこともでき、例えば「$x$の指数が偶数、$y$の指数が$3$の倍数」なら、$x$には$1,-1$、$y$には$1,u,u^2$を使えばよいわけです。

さらに先　生成関数とFPS

生成関数は、係数列をまとめて扱うための式

数列$a_0,a_1,a_2,\ldots$に対し、
$$ A(x)=\sum_{k=0}^{\infty}a_kx^k $$
と係数に並べたものを、その数列の通常型生成関数といいます。母関数とも呼ばれます。ある次数より先の係数がすべて$0$なら、有限多項式になります。
今回の$F(x,y)$も、二つの指数$a,b$に対応する場合の数を、$x^ay^b$の係数として並べた多変数の生成関数です。
式を作るだけでは、別の書き方で情報を並べただけです。そこに積や代入などの操作を加えると、場合の数を一つずつ求めずに、欲しい情報へまとめて働きかけられます。本記事では、

という対応を使いました。これが、生成関数を数え上げに利用する具体的な中身です。

FPSは「無限の係数列」として計算する

FPSはFormal Power Series、形式的冪級数の略です。以下では係数を実数や複素数として考えます。
$a_0+a_1x+a_2x^2+\cdots$を、ある数$x$を代入して値を求めるものとしてではなく、係数列$(a_0,a_1,a_2,\ldots)$を記録するものとして扱います。二つのFPSが等しいとは、すべての次数で係数が等しいことです。
足し算では同じ次数の係数を足します。掛け算は多項式と同じで、$A(x)=\sum_{k=0}^{\infty}a_kx^k$、$B(x)=\sum_{k=0}^{\infty}b_kx^k$なら、$A(x)B(x)$の$x^N$の係数を
$$ \sum_{k=0}^{N}a_kb_{N-k} $$
と定めます。重要なのは、一つの係数を決めるために足す項は有限個だということです。そのため、数値としての無限和の収束を仮定しなくても、各係数の計算ができます。
例えば$S(x)=1+x+x^2+\cdots$なら、$(1-x)S(x)$の定数項は$1$で、正の次数の係数はすべて$1-1=0$。したがって、FPSとして
$$ (1-x)S(x)=1,\qquad S(x)=\frac1{1-x} $$
と書けます。右の分数は「$1-x$を掛けると$1$になる形式的冪級数」を表しています。ここでは$x$に数値を入れていません。
多項式は、途中から係数がずっと$0$になるFPSです。そして生成関数は、数列や場合の数などを係数に記録して使うという役割を表す言葉です。「多項式・FPS」と「生成関数」は、互いに排他的な分類ではありません。

最初の問題を、もう一度思い返してみてください。平方数という条件を見て素因数の指数を追い、その指数を単項式へ記録し、偶数という条件に合わせて代入値を選びました。
次に場合の数の問題に出会ったら、「何を数えるか」に加えて、何を指数に記録すれば、その条件を取り出せるかも考えてみてください。多項式を作る最初の一手は、そこから始まります。
ここまでお読みくださり、ありがとうございました。
皆さんの日常に良き数学の彩のあらんことを。それでは、ごきげんよう。