2013

Sylvesterの問題(1)

sukarabe 2013年2月2日 (土) コメントはまだありません

Sylvesterの問題とか，Frobeniusの問題とか，Coin Problemとか，呼ばれている問題。$a$, $b$を互いに素な自然数とするとき，$0$個以上の1次結合 $ax+by$ ($x$, $y$は$0$以上の整数) の形で表すことの出来ない自然数$N$について，$N$の最大値と$N$の個数を求めよ，というもの。

Sylvesterが1882年にEducational Timesという雑誌(？)に投稿した記事とか，同じ年の論文とか，いろいろながめつつ，自分でも少し考えたりしたが，けっこう楽しめた。うん，面白い問題だ。

自分でも解いたのだが，それはまたあとで。母関数(Generating function)を利用する解法があって，面白かったのでメモ。

便宜上$N=0$も含めて考える。$ax+by$と表せる$0$以上の$N$について，$x$を $0 \leq x < b$ に制限すると，表し方はただ一通りになるから，\[ A(t)=\sum_{x=0}^{b-1} \sum_{y=0}^{\infty} t^{ax+by} = \sum_{N=0}^{\infty} a_N t^N \]を考えると，$N$が表せるときは$a_N=1$であり，表せないときは$a_N=0$となる。よって，$A(t)$はどの$N$が表せるかを表しているが，これは，\begin{align*} A(t) &= \sum_{x=0}^{b-1} t^{ax} \sum_{y=0}^{\infty} t^{by} = \frac{1-t^{ab}}{1-t^a}\cdot \frac{1}{1-t^b} \\ &= \frac{1-t^{ab}}{(1-t^a)(1-t^b)} \end{align*} とも表される。 一方，\[ B(t)=\sum_{N=0}^{\infty} t^N = \frac{1}{1-t} \]は，$0$以上のすべての整数を表しているから，差 \[ f(t)=B(t)-A(t)=\frac{1}{1-t}-\frac{1-t^{ab}}{(1-t^a)(1-t^b)} \] は，表されない$N$の全体を表している。つまり，\begin{align*} f(t) &= \sum_{\text{$N$:表されない}} t^N \\ &= \frac{(1-t^a)(1-t^b)-(1-t)(1-t^{ab})}{(1-t)(1-t^a)(1-t^b)} \end{align*} である。表されない$N$は有限個であるから，$f(t)$は$t$の多項式であり，その次数は表されない$N$の最大値である。また，$f(t)$の項の数は表されない$N$の個数となる。こうして，$f(t)$を調べることで，Sylvesterの問題を解くことが出来る。 以前に，$x+2y+3z=n$を満たす$0$以上の整数$x$, $y$, $z$の個数を求める問題で，Sylvesterが母関数 \[ \frac{1}{(1-t)(1-t^2)(1-t^3)} \] を用いているのを，Hardyの文章か何かで読んだことがあるが，まあ，同じようなことをやっているわけだ。