# Maximal number of monomials of multivariate polynomials.

If we consider multivariate polynomials of order $N$ and $n$ variables, how do we show that for the maximal number of monomials the following holds: $\binom{N+n}n$.

The hint our teacher gave was that number of monomials $=$ number of independent coefficients.

Thank you.

-
I am sorry, it should be N+n and not just N. I don't know how to write the code for that. The other n is correct. –  johnathan Jul 9 '12 at 21:24
Thanks for the correction. :) –  johnathan Jul 9 '12 at 21:27
A combinatorial approach is possible. You can find it in Evans's book on PDE, Problem 2. –  Giuseppe Negro Jul 9 '12 at 21:38
Hello, I couldn't really understand the relation between the two questions. Could you please help me out with this particular one? Thank you. –  johnathan Jul 9 '12 at 21:41
There is a well done article on the combinatorial problem in Wikipedia, called Stars and Bars. –  André Nicolas Jul 9 '12 at 22:50

Let $x_1, \ldots, x_n$ be the $n$ variables. The typical term of the polynomial has the form $$Cx_1^{k_1}x_2^{k_2}\cdots x_n^{k_n},$$ where each $k_i \geq 0$ and $$k_1 + \cdots + k_n \leq N.$$ Thus, the problem reduces to finding the number of $n$-tuples $(k_1, \ldots, k_n)$ satisfying this constraint. There are $\binom{N+n}{n}$ such $n$-tuples. This is a combinatorial exercise within the main exercise.
The main idea is to associate to each $n$-tuple an $n$-element subset of $\{1, \ldots, N + n\}$, namely $\{k_1 + 1, k_1 + k_2 + 2, \ldots, k_1 + k_2 + \cdots + k_n + n\}$. Once you've shown this is a bijection, the result follows.