Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
    
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
    
@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. – Giuseppe Negro Jul 10 '12 at 9:26

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|cite|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

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.