単純な場合の格子点の個数

math

格子点の個数がわからない
僕は組合せの話は知らない／分からないのですが、なぜか次のタイプの問題にしばしば遭遇します； R^nの第1象限 {(x_1, ..., x_n)∈R^n | x_1≧0, ..., x_n≧0 } の範囲で、非負整数kに対して、

  • 方程式 x_1 + ... + x_n = k
  • 不等式 x_1 + ... + x_n ≦ k

を考えます。この方程式／不等式の整数解（格子点）は何個あるんでしょう？ アルゴリズムとか近似とか評価とか漸化式とか母関数とかじゃなくて、nとkによるズバリあからさまな初等的表示が欲しいんですけど。そんなのないのかな？ どなたかご存知でしょうか。

上は, k個のボールとn-1個の仕切りの並べ方になるので, (n-1+k)!/k!(n-1)! = \left(\begin{array}n+k-1&\\k\end{array}\right).
下は, スラック変数x_{n+1}を突っ込んで, {x \in Z^{n+1} | x_1+...+x_n+x_{n+1}=k, x_{i}≧0 for all i}と方程式の解の個数に帰着出来て, \left(\begin{array}n+k&\\k\end{array}\right).

ということでコメント欄に[1..100]>=penさんが書いてる通りです.

ところで下の方って大学入試に出ましたっけねぇ?

簡単な拡張として,
\{(x_1, ..., x_n) \in \mathbb{R}^n | x_1 \geq 0, ..., x_n \geq 0, x_1 a_1 + \cdots + x_n a_n \leq k \} \cap \mathbb{Z}^n \}
の個数を数える問題が考えられます. a_i=1が元の問題です. n=2で母関数やら複素解析が出始めて, n=3だといやな関数になります.
より拡張すると, n次元空間の領域中の格子点を数え上げる問題になり,

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra (Undergraduate Texts in Mathematics)

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra (Undergraduate Texts in Mathematics)


と1冊の本になるんですって.
1章で, 上の簡単な拡張を扱っているそうで.