Simple Explicit Formula for Counting Lattice Points of Polyhedra

摘要

Given z ∈C~n and A ∈ Z~(m×n), we provide an explicit expression and an algorithm for evaluating the counting function h(y; z) := ∑ { z~x | x∈Z~n; Ax=y, x ≥ 0}. The algorithm only involves simple (but possibly numerous) calculations. In addition, we exhibit finitely many fixed convex cones of R~n explicitly and exclusively defined by A, such that for any y ∈ Z~m, h(y;z) is obtained by a simple formula that evaluates ∑ z~x over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.