1
$\begingroup$

If we consider a multivariate polynomial of $n$ variables with degree $N$, how do we show that the maximal number of monomials is $$\binom{N+n}{n} = \frac{(N+n)!}{n!\, N!}\quad ?$$

The hint our teacher gave was that the number of monomials is the number of independent coefficients. So how many independent coefficients does a multivariate polynomial have (at most)?

Thank you.

  • 0
    A combinatorial approach is possible. You can find it [in Evans's book on PDE](http://books.google.it/books?id=Xnu0o_EJrCQC&lpg=PP1&hl=it&pg=PA12#v=onepage&q&f=false), Problem 2.2012-07-09
  • 0
    Hello, I couldn't really understand the relation between the two questions. Could you please help me out with this particular one? Thank you.2012-07-09
  • 0
    There is a well done article on the combinatorial problem in Wikipedia, called [Stars and Bars.](http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29)2012-07-09
  • 0
    @johnathan: The combinatorial number determined in that Evans's exercise is the same as the number of monomials of degree $k$ in $n$ variables. The hint refers to the technique André Nicols mentions.2012-07-10
  • 4
    Possible duplicate of [Number of coefficients of multivariable polynomial](https://math.stackexchange.com/questions/380116/number-of-coefficients-of-multivariable-polynomial)2017-09-28

1 Answers 1

3

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.

  • 0
    As mentioned in the comments to the original post, one can find proofs of this in various introductory combinatorics books2012-07-09