■シルベスターの公式・フロベニウス数(その17)

 25セント,10セント,5セントの硬貨をそれぞれ少なくとも1つは使うDドルの両替の方法は,

  25q+10d+5n=100D−40

  5q+2d+n=20D−8

に対応するとしても等価である.

 3点(0,0),(a,0),(0,b)を頂点とする格子直角三角形内のの格子点の個数は,

  L={(a+1)(b+1)+gcd(a,b)+1}/2

となる.

  5q+2d+n=20D−8

のnを無視し,不等式

  5q+2d≦20D−8

を満たす組(q,d)を調べればよいのだが,

 a=(20D−8)/5,b=(20D−8)/2

として,(その4)の公式を適用するのは面倒で,虱潰しに数え上げた方が確実である.虱潰し法でも,少しの労力でリストアップすることができることを示しておきたい.

===================================

【1】n=3の場合の両替問題

 25セント,10セント,5セントの硬貨をそれぞれ少なくとも1つは使う1ドルの両替の方法は,

  25q+10d+5n=60

  5q+2d+n=12

に対応するとしても等価である.

  5q+2d+n=12

のnを無視し,不等式

  5q+2d≦12

を満たす組(q,d)を調べればよい.

 qは0〜2

[1]q=2のとき,dは0〜1の2通り

[2]q=1のとき,dは0〜3の4通り

[3]q=0のとき,dは0〜6の7通り

の13通りで

  I=20D^2−8D+1

に合致.

===================================

【2】n=4の場合の両替問題

 25セント,10セント,5セント,1セントの硬貨をそれぞれ少なくとも1つは使う1ドルの両替の方法は,

  25q+10d+5n+p=59

に対応するとしても等価である.

  25q+10d+5n+p=59

のpを無視し,不等式

  25q+10d+5n≦59

を満たす組(q,d,n)を調べればよい.

 qは0〜2の3通り.

[1]q=2のとき,dは0,nの0〜1の2通り

[2]q=1のとき,dは0〜3.

  a)d=3のとき,nは0の1通り

  b)d=2のとき,nは0〜2の3通り

  c)d=1のとき,nは0〜4の5通り

  c)d=0のとき,nは0〜6の7通り

[3]q=0のとき,dは0〜5

  a)d=5のとき,nは0〜1の2通り

  b)d=4のとき,nは0〜3の4通り

  c)d=3のとき,nは0〜5の6通り

  d)d=2のとき,nは0〜7の8通り

  e)d=1のとき,nは0〜9の10通り

  f)d=0のとき,nは0〜11の12通り

の60通りで

  IN=(50/3)N^3−(45/2)N^2−(53/6)N+1

に合致.

===================================