Results 1 to 2 of 2

Thread: 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 $\displaystyle p(n,k)$ and I tried an inductive approach to the problem , i.e, I was able to figure out that ,

    $\displaystyle p(n,1) = 1 $

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

    $\displaystyle 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 $\displaystyle 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
    12,028
    Thanks
    849

    Re: Partition Theory

    Hello, mathlover14!

    $\displaystyle \text{In how many ways can a positive integer }n$
    $\displaystyle \text{be broken into a sum of }k\text{ positive integers?}$
    $\displaystyle \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: $\displaystyle n = 8,\:k = 3$

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

    . . $\displaystyle \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;\_\;\circ \;\_\; \circ\;\_ \;\circ\;\_\;\circ $


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

    . . $\displaystyle \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;|\;\circ \;|\; \circ\;\_ \;\circ\;\_\;\circ $

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

    If the order is considered, the number of ways is: $\displaystyle {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: Feb 11th 2011, 08:22 PM
  2. partition help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 28th 2010, 03:35 AM
  3. set theory-partition
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 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: Mar 15th 2008, 08:57 PM

Search Tags


/mathhelpforum @mathhelpforum