Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 12, 2010 #1
    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!
     
  2. jcsd
  3. Feb 12, 2010 #2
    Re: combinatorics

    Sorry I don't know about combinatorics but that is hilarious.
     
  4. Feb 13, 2010 #3
    Re: combinatorics

    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.
     
    Last edited: Feb 13, 2010
  5. Feb 13, 2010 #4
    Re: combinatorics

    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 [itex]x^d[/itex]) 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 [itex]\leq d[/itex]. 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 [itex]d_1+d_2+\cdots+d_{n+1}=d[/itex] because then you can associate this tuple with the monomial,
    [tex](x_1)^{d_1}(x_2)^{d_2}\cdots(x_n)^{x_n}[/tex]
    It's a well-known fact in elementary combinatorics that there are [itex]\binom{n+d}{n}[/itex] 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 [itex]a_1 < a_2 < \cdots < a_n[/itex] 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
    [tex]d_1 =|\{1,\ldots,a_1-1\}|=a_1 -1[/tex]
    [tex]d_2=|\{a_1+1,a_1+2,\ldots,a_2-1\}|=a_2-a_1-1[/tex]
    [tex]d_3=|\{a_2+1,a_2+2,\ldots,a_3-1\}|=a_3-a_2-1[/tex]
    ...
    [tex]d_{n}=|\{a_{n-1}+1,a_{n-1}+2,\ldots,a_{n}-1\}|=a_{n}-a_{n-1}-1[/tex]
    [tex]d_{n+1}=|\{a_{n}+1,a_n+2,\ldots,n+d\}|=n+d-a_n[/tex]
    Then [itex]d_1+d_2+\cdots+d_{n+1} = d[/itex] and every such (n+1)-tuple can be uniquely chosen in this way.
     
  6. Feb 13, 2010 #5
    Re: combinatorics

    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).

    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.
     
  7. Feb 13, 2010 #6
    Re: combinatorics

    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.

     
  8. Feb 13, 2010 #7
    Re: combinatorics

    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 :)
     
  9. Feb 13, 2010 #8
    Re: combinatorics

    Ok so the difficulty is counting the number of (n+1)-tuples [itex](d_1,\ldots,d_{n+1})[/itex] 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 [itex]\binom{n+d}{n}[/itex] so the number of such (n+1)-tuples is [itex]\binom{n+d}{n}[/itex] 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.
     
  10. Feb 13, 2010 #9
    Re: combinatorics

    Thank you, your example helped a great deal
     
  11. Feb 13, 2010 #10
    Re: combinatorics

    I am glad your professor didn't tell you the answer, because as a result I have learnt 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 [tex]\mathcal{M}(n,d)[/tex] is the quantity that we seek.

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

    [tex]
    \frac{1}{1-x} = 1 + x + x^2 + x^3 + ...
    [/tex]

    Then :

    [tex]
    \frac{1}{1-x_1}\frac{1}{1-x_2}...\frac{1}{1-x_n} = (1+ x_1 + x_1^2 +
    x_1^3 +...)(1+ x_2 + x_2^2 + x_2^3 +...)...(1+ x_n + x_n^2 + x_n^3
    +...)
    [/tex]

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

    [tex]
    f(x) = \frac{1}{(1-x)^n} = 1+\sum_{i=1}^n\mathcal{M}(n,i)x^i
    [/tex]

    If [tex]f^{(n)}(x)[/tex] denotes the n-th derivative of [tex]f(x)[/tex] then :

    [tex]
    \mathcal{M}(n,i) = \frac{f^{(i)}(x)}{i!}|_{x=0}
    [/tex]

    But it is clear that :

    [tex]
    f^{(i)}(x)|_{x=0} = n.(n+1)...(n+i-1)
    [/tex]

    so that :

    [tex]
    \mathcal{M}(n,i) = \frac{(n+i-1)(n+i-2)...n}{i!}
    [/tex]

    i.e.

    [tex]
    \mathcal{M}(n,i) = \binom{n+i-1}{n-1}
    [/tex]
     
    Last edited by a moderator: Apr 24, 2017
  12. Mar 5, 2010 #11
    Re: combinatorics

    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!
     
  13. Mar 6, 2010 #12
    Re: combinatorics

    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 [tex] \binom{n+d}{n} [/tex] in this way??
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of monomials of degree d in finite field F[x]
Loading...