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.

  • 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 books2019-01-31