母関数
- 無限数列を係数に持つ関数
- フィボナッチ数列(こちらから、Sequence ID = A000045)の母関数は $F(z)=\frac{z}{1-z-z^2}$
- 等比級数( $1,x,x^2,...$ )のそれは $F(x)=\frac{1}{1-x}$
上記、母関数の導出には部分分数分解を使った
部分分数分解
- $F(z)=\frac{p(z)}{\prod_{k=1}^m (z-a_k)^{e_k}$ は多項式 $p(z)$ の次数が $\sum_{k=1}^m e_k$ 未満のときに
- $F(z)=\sum_{k=1}^m (\sum_{i=1}^k \frac{c_{k,i}}{(z-a_k)^i} )$ と分解されることを言う
Frobeniusの硬貨交換問題
- 「互いに素な正整数として与えられた金種 $a_1,a_2,...,a_d$ に対して、 $a_1,a_2,...,a_d$ の硬貨を用いて支払えない最高額はいくらか
- この最高額の数をFrobenius数と言う
  - $d=2$ の場合には、Frobenius数は $g(a_1,a_2)=a_1\times a_2 -a_1 -a_2$
Sylvesterの定理：のときのFrobenius数に関連して、次のことも言える
- 「正整数 $a_1,a_2$ が互いに素なとき、1と $(a_1-1)\times (a_2-1)$ の間にある整数のうちのちょうど半分の額が、『支払える額』である」
分割
- $(m_1,...,m_d) \in \mathbf{Z}^d$ は、 $d$ 次元の自然数空間(正の側の格子点の集合)を表す。
- $m_j \ge 0$ , $\sum_{j=1}^d m_j d_j=n$ ( $n$ は自然数)の制約を入れるとこれは、制限分割と呼び、制限分割の数を表す関数を制限分割関数( $p_A(n)$ )と言う
- Frobenius数は $p_A(n)=0$ を満たす最大数 $n$ のこと
制限分割関数は、幾何学的には、次のように言える
- $(x_1,...,x_d)\in \mathbf{R}^d$ が $d$ 次元有理数空間で、その中で $x_j \ge 0$ , $\sum_{j=1}^d x_j a_j=1$ を満足するような部分空間は、ある大きさの凸包を作るが、それを各方向に $n$ 倍伸ばしたもの(第 $n$ 伸長(dilate)と言う)の中の整数座標の点の数が制限分割関数の値である
の場合の制限分割関数(が互いに素な２つの数とする)を考える
- $(\frac{1}{1-z^a})(\frac{1}{1-z^b})=(1+z^a+z^{2a}+...)(1+z^b+z^{2b}+...)$ なので
- $(\frac{1}{1-z^a})(\frac{1}{1-z^b})=\sum_{k\ge 0}\sum_{l\ge 0} z^{ak}z^{al} = \sum_{n\ge 0} p_{a,b}(n) z^n$ となって、 $p_{a,b}(n)$ が現れる
- ここで、 $z^a=1$ , $z^b=1$ の解を $\xi_a = e^{\frac{2\pi i}{a}}=\cos (\frac{2\pi}{a}) + i \sin (\frac{2\pi}{a})$ （ $b$ の方も同様)として考えることで次の式を得る
Popoviciuの定理
- - ただし、{}は小数部分を取り出す関数、は,を満たす整数
    - ここで"mod"関数が出てくるのは、「割り切れれば格子点が『線の上』になる」という意味合い
    - そして「少数部分」が補正項としてでるのは、「少数以外の部分」は「割り算をして格子点を含むことができるかどうかに反映できた部分」であるのに対し、「少数部分」はそれが難しいという意味合い
- $p_{a,b}(n)+p_{a,b}(ab-n)=1$ なる関係がある
３枚以上への拡張
- 考え方は同じ
- [tex:p_A(n)=\sum_{i=1}^d *1;a_i)]
  - ただし、 $B_i$ は部分分数分解で出てくる係数(部分分数分解する前の式は $f(z)=\frac{1}{(1-z^{a_i})...(1-z^{a_d})z^n$ である)
  - また、はを表し、はFourier-Dedekind和と呼ばれ
    - $s_n(a_1,a_2,...,a_,;b)=\frac{1}{b} \sum_{k=1}^{b-1} \frac{\xi_b^{kn}}{(a-\xi_b^{ka_i})(a-\xi_b^{ka_2})...(a-\xi_b^{ka_m})}$