Proposition 15

Let $n$ and $h$ be integers and let E be a set with $h$ elements. Then the number of mappings $u$ of E into $[0, n]$ such that $\sum_{x \in E} u(x) \leqslant n$ (resp. $\sum_{x \in E} u(x) = n$, for $h > 0$) is

Let $A(h, n)$ (resp. $B(h, n)$) denote the number of mappings $u$ of E into $[0, n]$ such that $\sum_{x \in E} u(x) \leqslant n$ (resp. $\sum_{x \in E} u(x) = n$ for $h > 0$). We show first that $A(h-1, n) = B(h, n)$. For this, let E′ be a subset of E with $h - 1$ elements, and let $\{a\} = E - E'$. If $u$ is a mapping of E into $[0, n]$ such that $\sum_{x \in E} u(x) = n$, then its restriction $u'$ to E′ is such that $\sum_{x \in E'} u'(x) \leqslant n$, and moreover $u(a) = n - \sum_{x \in E'} u'(x)$. Conversely, every mapping $u'$ of E′ into $[0, n]$ which satisfies $\sum_{x \in E'} u'(x) \leqslant n$ defines a unique mapping $u$ of E into $[0, n]$, of which $u'$ is the restriction, and which is such that $\sum_{x \ni E} u(x) = n$.

We note next that if $\sum_{x \in E} u(x) \leqslant n$, then either $\sum_{x \in E} u(x) = n$, or else $\sum_{x \in E} u(x) \leqslant n-1$, and these two possibilities are mutually exclusive. Consequently

Since $A(0, 0) = 1 = \binom{0}{0}$, the formula $A(h, n) = \binom{n+h}{h}$ follows from above and from Proposition 13, by induction on $n + h$.

\* The number of monomials $X_1^{\alpha_1} X_2^{\alpha_2} \ldots X_h^{\alpha_n}$ in $h$ indeterminates with total degree $\leqslant n$ is evidently equal to the number of mappings $i \rightarrow \alpha_i$ of $[1, h]$ into $[0, n]$ such that $\sum_{i=0}^{h} \alpha_i \leqslant n$, and is therefore equal to $\binom{n+h}{h}$ by Proposition 15; this number is also the number of monomials in $h + 1$ indeterminates with total degree $n$. \*