Results 1 to 2 of 2

Math Help - Writing n as a sum of integers

  1. #1
    Junior Member
    Joined
    Feb 2009
    From
    London
    Posts
    39
    Thanks
    1

    Writing n as a sum of integers

    Hey,

    I have been given a problem that at first seemed quite trivial but on further inspection seems to be quite hard. If n is a non-negative integer, in how many ways is it possible to write

    n=a+2b+3c

    for non-negative integers a, b, c.

    clearly, if i fix some 0<c<floor(n/3), then i have n-3c choices for a and b, but i'm not sure how to proceed. I also thought it could be calculated using a recurrence relation, but I'm particularly rusty in that area of combinatorics. Any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by hairymclairy View Post
    I have been given a problem that at first seemed quite trivial but on further inspection seems to be quite hard. If n is a non-negative integer, in how many ways is it possible to write
    n=a+2b+3c for non-negative integers a, b, c.
    This is not a simple formula. It can be done with generating functions.
    Expand the following: \left( {\sum\limits_{k = 0}^n {x^k } } \right)\left( {\sum\limits_{k = 0}^n {x^{2k} } } \right)\left( {\sum\limits_{k = 0}^n {x^{3k} } } \right).
    The coefficient of the x^n answers your question.
    Working with a computer algebra system that is doable.
    With a CAS you could let f(x)= \left( {\sum\limits_{k = 0}^n {x^k } } \right)\left( {\sum\limits_{k = 0}^n {x^{2k} } } \right)\left( {\sum\limits_{k = 0}^n {x^{3k} } } \right) then \displaystyle\frac{1}{{n!}}\frac{{d^n f}}{{dx^n }}(0) will give you the same answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 6th 2011, 12:47 AM
  2. Replies: 7
    Last Post: August 3rd 2010, 02:31 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 03:02 PM
  4. Replies: 4
    Last Post: February 24th 2008, 04:08 PM
  5. Replies: 2
    Last Post: October 14th 2007, 04:18 PM

Search Tags


/mathhelpforum @mathhelpforum