Number of monomials of degree d in finite field F[x]

[mathstime]

Prove that the number of monomials of degree d in finite field F[x] is \binom{n+d}{n}

This is not so much a homework question as something I have read and asked my professor about. He said it was too easy and that I should be able to do it and wouldn't help me. I know I'm probably being a bit blind - any guidance welcomed!

 

[Phyisab****]

Sorry I don't know about combinatorics but that is hilarious.

 

[mathstime]

That isn't very kind.

I thought this site was supposed to encourage learning?

If I want to get into university to do a mathematics degree, I need to feel like I can ask for help.

 

[rasmhop]

I must admit I'm not sure if I totally understand the OP, but as he hasn't gotten any answers to his question I'll try.

I usually take F[x] to mean the polynomial ring in ONE variable, and in that case there is one monomial if you require it to be monic (namely $x^d$) and |F|-1 if not (the same but with a non-zero constant). However your sought expression suggests you are actually looking for the number of monic monials in n variables of degree $\leq d$. In that case what you actually do is count the number of (n+1)-tuples [itex](d_1,d_2,\ldots,d_{n+1})[/tex] of non-negative integers such that $d_1+d_2+\cdots+d_{n+1}=d$ because then you can associate this tuple with the monomial,<br /> $$(x_1)^{d_1}(x_2)^{d_2}\cdots(x_n)^{x_n}$$<br /> It's a well-known fact in elementary combinatorics that there are $\binom{n+d}{n}$ such (n+1)-tuples. If you confirm that this is actually the problem you're working on, then I can expand on how to derive this, but at this point I don't really want to write a lot that may turn out to be useless. The basic idea is that we choose n integers $a_1 < a_2 < \cdots < a_n$ out of [itex]\left{1,2,\ldots,n+d\right}[/tex] and then we think of the a_i as barriers count the number of integers between the barriers, so let <br /> $$d_1 =|\{1,\ldots,a_1-1\}|=a_1 -1$$<br /> $$d_2=|\{a_1+1,a_1+2,\ldots,a_2-1\}|=a_2-a_1-1$$<br /> $$d_3=|\{a_2+1,a_2+2,\ldots,a_3-1\}|=a_3-a_2-1$$<br /> ...<br /> $$d_{n}=|\{a_{n-1}+1,a_{n-1}+2,\ldots,a_{n}-1\}|=a_{n}-a_{n-1}-1$$<br /> $$d_{n+1}=|\{a_{n}+1,a_n+2,\ldots,n+d\}|=n+d-a_n$$<br /> Then $d_1+d_2+\cdots+d_{n+1} = d$ and every such (n+1)-tuple can be uniquely chosen in this way.[/itex][/itex]

 

[rasmhop]

I thought this site was supposed to encourage learning?

I don't think Phyisab**** meant to be offensive, but rather to put out that it's kind of crazy to get such an answer from a professor. Personally I don't think that response (from the professor) was appropriate unless you're in an extremely advanced graduate class (he could at least have kindly pointed you in the way of some extra material).

If I want to get into university to do a mathematics degree, I need to feel like I can ask for help.

You're in high school and a teacher/professor thinks this is too simple for you? I'm sorry, but then that person is likely slightly delusional.

 

[mathstime]

Ramshop, thank you for your help. This problem is still quite confusing to me, but the way you have laid it out is starting to make sense.

It's a well-known fact in elementary combinatorics that there are $\binom{n+d}{n}$ such (n+1)-tuples. If you confirm that this is actually the problem you're working on, then I can expand on how to derive thisQUOTE]

Yes, this is the problem. Sorry, maybe I meant to write F[x_1,...,x_n]?

My professor (yes cruel, but pushes my learning!) said it was a combinatorial exercise, and king of implied there was an easy solution?

 

[mathstime]

And just to clarify, I am not actually in high school anymore, I have left and been working for some years, but would like to go back to school to study maths, so have been taking some outside classes and reading around a bit. Your help is much appreciated :)

 

[rasmhop]

Ok so the difficulty is counting the number of (n+1)-tuples $(d_1,\ldots,d_{n+1})$ of non-negative integers. I think I actually gave the necessary details in the previous post, but it may be hard to visualize so let me provide an example. To visualize the strategy imagine you have n=3 and d=6. Then you choose among n+d=9 objects:
123456789
Now we want to split these objects into n+1=4 parts which takes n=3 dividers. For instance (2,1,0,3) is:
12|4||789
so 3,5,6 has been chosen and we don't choose them with regards to order as we reorder them afterwards so it would introduce double counting. Intuitively it's pretty clear that every (n+1)-tuple with sum d can be represented in this way. In this way it's pretty clear that we have to choose n dividers out of n+d numbers. This leaves n+d-n=d numbers to be actually counted so the tuple will have sum d. The number of ways to choose n objects out of n+d is $\binom{n+d}{n}$ so the number of such (n+1)-tuples is $\binom{n+d}{n}$ since every such (n+1)-tuple can be chosen in exactly one way using this procedure.

If you feel anything about this construction is unclear, feel free to ask.

 

[mathstime]

Thank you, your example helped a great deal

 

[aracharya]

I am glad your professor didn't tell you the answer, because as a result I have learned something new from your post:)

My approach was different. I was motivated by http://en.wikipedia.org/wiki/Partition_(number_theory)#Generating_function".

In the below $$\mathcal{M}(n,d)$$ is the quantity that we seek.

We know that for $$|x|<1$$, we have the following (unique) power series expansion :

$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + ...$$

Then :

$$\frac{1}{1-x_1}\frac{1}{1-x_2}...\frac{1}{1-x_n} = (1+ x_1 + x_1^2 +<br /> x_1^3 +...)(1+ x_2 + x_2^2 + x_2^3 +...)...(1+ x_n + x_n^2 + x_n^3<br /> +...)$$

If we have a term $$x_1^{a_1}x_2^{a_2}...x_n^{a_n}$$, then let the net order correspond to the quantity $$a_1 + a_2 + ... + a_n$$. If, in the power series above, we aggregate all the terms with net order $$d$$, then let the number of such terms be equal to $$\mathcal{M}(n,d)$$. From this it is clear that if we set $$x_1 = x_2 = ... = x_n$$ then the coefficient of $$x^d$$ in the power series expansion of $$1/(1-x)^n$$ will be equal to $$\mathcal{M}(n,d)$$. That is :

$$f(x) = \frac{1}{(1-x)^n} = 1+\sum_{i=1}^n\mathcal{M}(n,i)x^i$$

If $$f^{(n)}(x)$$ denotes the n-th derivative of $$f(x)$$ then :

$$\mathcal{M}(n,i) = \frac{f^{(i)}(x)}{i!}|_{x=0}$$

But it is clear that :

$$f^{(i)}(x)|_{x=0} = n.(n+1)...(n+i-1)$$

so that :

$$\mathcal{M}(n,i) = \frac{(n+i-1)(n+i-2)...n}{i!}$$

i.e.

$$\mathcal{M}(n,i) = \binom{n+i-1}{n-1}$$

 

[mathstime]

Hi aracharya

Thanks for your input! Your example confuses me a little, but the more I read over it, the more it starts to make sense. Can you summarize what you are doing??

Also, how come you end up with (n-1)'s in your final line? Sorry if I'm just being silly!

 

[mathstime]

Ok, I can now successfully work through that answer - thank you for you help.

I just have one question remaining. Why can we not show that it is equal to $$\binom{n+d}{n}$$ in this way??