Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 1 more comment

1 Answer

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.

share|improve this answer
    
As mentioned in the comments to the original post, one can find proofs of this in various introductory combinatorics books –  Hugh Denoncourt Jul 9 '12 at 21:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.