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

 4点(0,0,0),(1,0,0),(0,1,0),(0,0,1)を頂点とする三角錐のn拡大の格子点の個数は,

  Ln=(n+1)(n+2)(n+3)/6

となる.

 ここでは,4種類の硬貨25セント,10セント,5セント,1セントを用いて,1ドルを両替する方法は何通りあるかを考えてみよう.

  [参]TSマイケル「離散数学パズルの冒険」青土社

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

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

  25q+10d+5n+p=100D=50N

のpを無視し,不等式

  5q+2d+n≦20N

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

 それに対応する格子直角三角錐は,4点(0,0,0),(2,0,0),(0,5,0),(0,0,10)で体積は50/3となる.また,

  L=49,I=2,B=47

より,

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

 4種類の硬貨25セント,10セント,5セント,1セントを用いて,1ドルを両替する方法は,N=2とおくと,242通りある.

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

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

  25q+10d+5n+p=100D=50N

のpを無視し,不等式

  5q+2d+n≦10N

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

 それに対応する格子直角三角錐は,4点(0,0,0),(2,0,0),(0,5,0),(0,0,10)で体積は50/3となる.また,

  L=49,I=2,B=47

より,

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

 4種類の硬貨25セント,10セント,5セント,1セントを用いて,1ドルを両替する方法は,N=2とおくと242通りある.

 また,これらの硬貨をそれぞれ少なくとも1つは使う両替の方法は,三角錐内部の格子点に対応する.n=3の場合は中央項の符号が反転したが,n=4の場合は中央2項の符号が反転する.

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

 1ドルを25セント,10セント,5セント,1セントをそれぞれ少なくとも1つは用いて両替する方法は60通りあるというわけである.これくらいの数であれば,虱潰しに数え上げた方が着実であるといえるかもしれないが・・・.

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