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

Count the number of integer solutions

  1. Nov 17, 2005 #1

    benorin

    User Avatar
    Homework Helper

    Count the number of integer solutions of (rather, # of integer lattice points such that)

    [tex]n+\sum_{k=1}^{n} \left| x_{k}\right| \leq N[/tex]

    Not homework, so no rush. I have worked it through before with a prof., but he's so brilliant I didn't understand much of anything he said :redface: . His solution involed a generating function, something like the coefficient of the blah term in the expansion of blahblah.

    Note that the LHS is the height of a polynomial with integer coefficients, although it has nothing to do with the solution.
     
    Last edited: Nov 17, 2005
  2. jcsd
  3. Nov 17, 2005 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    If n > N, the answer is 0. Otherwise, the problem reduces to finding the lattice point solutions of:

    [tex]\sum _{k=1} ^n |x_k| \leq N'[/tex]

    where N' > 0. Let f(N',n) denote the number of solutions. Then we want to find f(N',n) and this is just:

    [tex]f(N',n) = f(N',n-1) + 2\sum _{k=1} ^{N'} f(N'-k,n-1)[/tex]

    We get this because [itex]\sum _{k=1} ^n |x_k| = |x_1| + \sum_{k=2} ^n |x_k|[/itex] and when |x1| > 0, then x1 has two possible values whereas when |x1| = 0 then x1 = 0 only. It's a start.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Count the number of integer solutions
Loading...