On vector partition functions (Q1903011): Difference between revisions

Let \(\mathbb{N}\) be the set of nonnegative integers and \(A = (a_1, \dots, a_n)\) a \(d \times n\)-matrix with entries in \(\mathbb{N}\). The corresponding vector partition function \(\varphi_A : \mathbb{N}^d \to \mathbb{N}\) is defined as follows: \(\varphi_A (u)\) is the number of integer vectors \((\lambda_1, \dots, \lambda_n) \in \mathbb{N}^n\) such that \(\lambda_1 a_1 + \cdots + \lambda_n a_n = u\). It was shown by \textit{G. R. Blakley} [Duke Math. J. 31, 341-345; Erata ibid. 718 (1964; Zbl 0122.01501)] that there exists a finite decomposition of \(\mathbb{N}^d\) such that \(\varphi_A\) is a polynomial of degree \(n - d\) on each piece. Here such a decomposition into ``chambers'' is described explicitly, and within each chamber a formula is given. The corresponding theorem provides a generalization of the theory of ``denumerants'' (the \(d = 1\) case). The proof rests on a formula due to Peter McMullen for counting lattice points in rational convex polytopes.