Results 1 to 2 of 2

Math Help - Partition Theory

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    14

    Partition Theory

    In how many ways can a positive integer n be broken into a sum of k positive integers ? ( While representing the number as a sum the order in which the addends are arranged for each of the ways is not taken into consideration)

    I know that we denote the number of ways to do this as p(n,k) and I tried an inductive approach to the problem , i.e, I was able to figure out that ,

    p(n,1) = 1

    p(n,2) = \left\lceil\frac{n-1}{2}\right\rceil

    p(n,3) = \sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor} {\left\lceil\frac{i-1}{2}\right\rceil + \left\lceil\frac{n-i-1}{2}\right\rceil }

    But I cant seem to figure out p(n,4) and so on....And I need a closed-form solution, not recurrence relations..So, please help . Thanks in advance .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    643

    Re: Partition Theory

    Hello, mathlover14!

    \text{In how many ways can a positive integer }n
    \text{be broken into a sum of }k\text{ positive integers?}
    \text{(The order in which the addends are arranged is not considered.)}

    Note: The following does not answer the question.

    If the order of the addends is considered, there is a simple approach.


    Consider: n = 8,\:k = 3

    Place the 8 objects in a row, leaving a space between them.
    . . There are: n-1\,=\,7 spaces.

    . . \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;\_\;\circ \;\_\; \circ\;\_ \;\circ\;\_\;\circ


    Select 2 of the 7 spaces and insert "dividers".
    . . There are: k-1\,=\,2 dividers.

    . . \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;|\;\circ \;|\; \circ\;\_ \;\circ\;\_\;\circ

    This diagram represents: 4 + 1 + 3 \:=\:8

    If the order is considered, the number of ways is: {n-1\choose k-1}


    Can we eliminate the duplication included in this method?
    I don't know . . . I've tried and failed.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. homeomorphism from a partition of R^2 to (S^1) x (S^1)
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 11th 2011, 08:22 PM
  2. partition help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 28th 2010, 03:35 AM
  3. set theory-partition
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2008, 02:14 PM
  4. Partition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2008, 02:39 AM
  5. Partition help!!!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 15th 2008, 08:57 PM

Search Tags


/mathhelpforum @mathhelpforum