Results 1 to 4 of 4

Math Help - partition of an integer

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    17

    Question partition of an integer

    Suppose d,n \in N with n \leq d. Then find the number of ways in which d=r_1+ \cdots + r_k with r_1,...,r_k \in N \cup \{0\} and r_i \leq n for all i=1,\ldots ,k
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Rougher problem than it looks...

    You do realize that the partition function P(n), the number of ways a natural number n can be partitioned as the sum of smaller numbers, is given by Hardy and Ramanujan's complicated formula:

    P(n)=\frac1{\pi\sqrt2}\sum_{k=0}^\infty A_k(n)\sqrt{k}\frac d{dn}\left[\frac{\sinh\left(\frac\pi{k}\sqrt{\frac23(n-\frac1{24})}\right)}{\sqrt{n-\frac1{24}}}\right]

    where <br /> <br />
A_k(n)=\sum_{h=1}^k\delta_{gcd(h,k),1}exp\left[\pi i\sum_{j=1}^{k-1}\frac{j}k\left(\frac{hj}{k}-\lfloor\frac{hj}{k}\rfloor-\frac12\right)-\frac{2\pi i h n}{k}\right]<br /> <br />

    Are you attempting to place an upper limit on the highest addend r_i in effort to simplify this formula? Or do you seek an algorithmic solution?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    17

    problem with additional constraints

    Thanks for your reply.
    In P(d) there is no restriction on the number of r_i's.
    But in my question each partition of d must have exactly n values (including repetitions) and all those partitioned values ( r_i's) must be \leq n.

    Is there any formula for such a case ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by thippli View Post
    Thanks for your reply.
    In P(d) there is no restriction on the number of r_i's.
    But in my question each partition of d must have exactly n values (including repetitions) and all those partitioned values ( r_i's) must be \leq n.

    Is there any formula for such a case ?
    I've derived a formula (unless I've made an embarrassing mistake) ... but it is not nice ( beware, for it may cause irreversible damage in you )
    Spoiler:

    <br />
\sum\limits_{1 \leqslant k \leqslant d} {\sum\limits_{j \geqslant 0} {\binom{k}{j}\left( { - 1} \right)^j \binom{k+d-j\cdot {(n+1)}-1}{k-1}} } <br />


    Sketch of the Proof:
    Spoiler:

    Our solution is the coefficient of x^d in the following polynomial: <br />
\sum\limits_{1 \leqslant k \leqslant d} {\left( {1 + x + ... + x^n } \right)^k }  = \sum\limits_{1 \leqslant k \leqslant d} {\left( {\tfrac{{1 - x^{n + 1} }}<br />
{{1 - x}}} \right)^k }  = \sum\limits_{1 \leqslant k \leqslant d} {\left( {\tfrac{1}<br />
{{1 - x}}} \right)^k \left( {1 - x^{n + 1} } \right)^k } <br />
    Now write both, <br />
{\left( {\tfrac{1}<br />
{{1 - x}}} \right)^k }<br />
and <br />
{\left( {1 - x^{n + 1} } \right)^k }<br />
as power series and multiply them and pick the coefficient of x^d. Then sum over k
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 04:16 AM
  2. partition help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 28th 2010, 04:35 AM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 01:20 PM
  5. Partition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2008, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum