Results 1 to 2 of 2

Math Help - Help with integer partitions

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    53
    Thanks
    1

    Help with integer partitions

    I'm still new to integer partition and I've gotten this far.
    The number of order independant ways you can partition an integer into a set of numbers whose sum is N is defined as P(n).
    Some examples are P(5)=7, P(8)=22 , and P(10)=42.

    Let P(n,k) be the number of partitions in which each member is at least k. Also this is congruent to the number of partitions with at least k members.

    P(n,k) = 0\ if \ k>n
    P(n,k) = 1\ if\ k=n
    P(n,k) = P(n,k+1) + P(n-k,k)

    If I say P(10,5) that is the set of all partitions of 10 whose members are all >=5.
    Which in this case (10,5)=2. 10 and 5+5.

    Is there a way to find the partitions of X in which all the members <=K ? I've been trying to figure out some way to add and/or subtract various P(n,k) values to achieve this but i'm at a lost.

    I did see some pages on the generating functions of P(n), but I haven't fully understood them yet. Am I going to be forced to use the generating function to get what I want? Namely the number of Partitions of X whose members are all <= to some K
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Help with integer partitions

    Do you know the 'little book' MATHEMATICS OF CHOICE by Ivan Niven?
    There is a very nice discussion of this topic in that book.
    I have programmed MathCad to produce a table of partitioning an integer N into k or fewer summands. The recursion used is similar to the one you posted.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 03:16 AM
  2. partitions
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 15th 2010, 04:22 PM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 12:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  5. Generating Functions and Integer Partitions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 9th 2008, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum