検索用コード
nを自然数とする.\ x+y+z\leqq n,\ x\geqq0,\ y\geqq0,\ z\geqq0を満たす整数解の組数を求めよ.$ \\
座標空間の格子点の個数(整数解の組数)
整数解の組数は,\ 図形的にとらえると格子点の個数である. \\[.2zh] 本問はx,\ y,\ zの3変数なので,\ 座標空間における格子点の個数を数えることになる. \\[.2zh] 座標平面の格子点の個数は,\ 直線上の格子点の個数をΣ計算して求められた. \\[.2zh] 座標空間の格子点の個数は,\ \bm{平面上の格子点の個数をΣ計算する}ことで求められる. \\[.2zh] これは,\ 平面上の面積を積分すると体積が求まるのと同様である. \\[1zh] まず,\ 不等式が表す立体を\bm{平面z=kで切断したときの断面にある格子点を数える.} \\[.2zh] このとき,\ 不等式が表す立体の形をイメージできる必要はない(もちろんできた方がよい). \\[.2zh] \bm{断面の形ならば数式だけでわかる}からである. \\[.2zh] z=kのとき,\ 問題の不等式はy\leqq -\,x+n-k,\ x\geqq0,\ y\geqq0となる. \\[.2zh] n,\ kは単なる定数であるから,\ 直角を挟む2辺の長さがn-kの直角二等辺三角形を表す(左図). \\[.2zh] この領域内にある格子点の個数を数えればよい.\ \bm{対称性を利用して図形的に求める}のが簡潔である. \\[.2zh] つまり,\ 一旦長方形を持ち出せばよいが,\ 単純に半分ではないことに注意する. \\[.2zh] (z=k上の格子点)=(赤)+(緑)=\bunsuu{(長方形)-(緑)}{2}+(緑) \\[.8zh] 長方形の1辺にある格子点の個数はn-k+1個である. \\[.2zh] 対角線上の格子点の個数もn-k+1個である. \\[.2zh] 展開せず,\ 因数分解する方向で整理するとよい. \\[1zh] 本問の不等式が表す立体は,\ 以下の知識があると瞬時にイメージできる. \\[.2zh] 一般に,\ 座標空間で\ \bunsuu xa+\bunsuu yb+\bunsuu zc=1は3点(a,\ 0,\ 0),\ (0,\ b,\ 0),\ (0,\ 0,\ c)を通る平面を表す. \\[.8zh] 実際,\ 3点を代入すると成り立つ.\ そして,\ 3点が定まると平面はただ1つに定まる. \\[.2zh] ちなみに,\ 座標平面において,\ \bunsuu xa+\bunsuu yb=1は2点(a,\ 0),\ (0,\ b)を通る直線を表す. \\[.8zh] 与式は\ \bunsuu xn+\bunsuu yn+\bunsuu zn=1と変形でき,\ これは(n,\ 0,\ 0),\ (0,\ n,\ 0),\ (0,\ 0,\ n)を通る平面である. \\[.8zh] x\geqq0,\ y\geqq0,\ z\geqq0と合わせて右図の立体を表すことがわかる. \\[1zh] 平面z=k上の格子点の個数が求まれば,\ 後はz=0からz=nまでのΣ計算である. \\[.2zh] (求める格子点)=(平面z=0上の点)+(平面z=1上の点)+\cdots\cdots+(平面z=n上の点) \\[1zh] このΣ計算はまともにやるとやや面倒である(別解1). \\[.2zh] nは定数扱いなので,\ kで整理してΣ公式を適用する. \\[.2zh] ただし,\ Σ公式はk=1からでなければ適用できないから,\ \bm{k=0のときを分割}する必要がある. \\[1zh] かなり技巧的だが,\ 本解のように求めるのが簡潔である.\ まず,\ Σを次のように変換できる.
この後\retuwa{k=1}{n+1}(k^2+k)としてΣ公式を適用してもよいが,\ さらにスマートな方法がある. \\[.8zh] \bm{連続整数の積の和が階差の形に変形できる}ことを利用するのである. \\[.2zh] 一般に,\ k(k+1)=\bunsuu13\{k(k+1)(k+2)-(k-1)k(k+1)\}\ 等が成立した. \\[.6zh] そして,\ 一般項を階差の形で表すことができれば,\ 以下のようにして和を求められるのであった. \\[.2zh] k(k+1)(k+2)-(k-1)k(k+1)\
実は,\ x,\ y,\ zが対等な本問は,\ 場合の数の問題として解くのが最も簡潔である(別解2). \\[.2zh] 4つめの文字wを用いて等式に変換する非常に巧妙な手法である. \\[.2zh] 詳細は場合の数分野で説明したので,\ ここでは概要を掲載するに留める.