Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to my previous question, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ for decompositions of $n$ with exactly two members, for 13 we have $\{10,3\}$ , $\{9,4\}$,.... What about the number of decompositions of $n$ with exactly $i$ members?
It is clear that because the members are at least three, $i$ is smaller than $\lfloor \frac{n}{3} \rfloor$.

share|improve this question
    
there is a recursion $P(n,k)=P(n-1)+P(n-k,k)$ according to mathworld.wolfram.com/PartitionFunctionP.html where there are also some explicit formulas for small $k$ –  yoyo Apr 16 '11 at 14:48
    
There is a Java calculator for this and some other constrained partitions and compositions. –  Henry Apr 16 '11 at 15:09

3 Answers 3

up vote 2 down vote accepted

We have that there is a correspondence between integer partitions with exactly k summands and integer partitions with largest term equal to k. So, if you're familiar to generating functions, one can find one.Here's how.

Note that $1/(1-x) = 1+x+x^2+x^3+...= \sum_{i=0}^\infty x^i$. Also, note that: $1/(1-x^2) = 1+x^2+x^4+...=\sum_{i=0}^\infty x^{2i}$. A natural would now be to answer, then what's $1/((1-x)(1-x^2))$, in terms of a formal power series? By some manipulations, we can see that the first terms are $1+x+2x^2+2x^3+3x^4+3x^5$. The coefficient of $x^n$ here will count the number of partitions of n, with at most 2 summands. Generalizing, we have that coefficient of $x^n$ in the expansion of: $1/((1-x)(1-x^2)(1-x^3)\cdots (1-x^k)$ counts the number of partitions of n, into at most k summands, or equally, the number of partitions of n with no part larger than k. Now, however, you want to know how many has exactly k summands.

So, one can see that this is the same as the coefficient of $x^n$ in $x^k/(1-x)(1-x^2)\cdots (1-x^k)$, the number of partitions with at least one part equal to k. To show how this applies to your example: $x^2/((1-x)(1-x^2))$, then the coefficient of $x^13$ is 6. The partitions it corresponds to are $(10,3)$,$(9,4)$,$(7,6)$ ,$(11,2)$,$(12,1)$,$(8,5)$. So this agrees well.

If you want some further intuition for generating functions, I would suggest that you check out generatingfunctionology by Wilf (http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf), and for Integer partitions, I know that George E. Andrews has written a book on it, but I haven't personally read it, although I've heard that it should be good.

share|improve this answer
    
Wilf has also compiled lecture notes explicitly dealing with partitions and generating functions here: math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf The result Dedalus mentions is Theorem 1. –  01000100 Jan 18 '12 at 10:01

As far as exact nonrecursive formulae, I don't think there any as of yet. But I can point you to a couple of results which are asymptotic approximations and a recursion which will give you an exact answer.

The first, stated above, is the recursion $P(n,k) =P(n-1,k-1)+P(n-k,k)$ where $P(n,k)$ is the number of partitions of $n$ with exactly $k$ summands.

As far as asymptotic formulae the partitions my favorite approximation is the result of Erdos and Lehner $ \sum_{j=1}^k P(n,j) \thicksim \frac{1}{k!} {n-1 \choose k-1} $ so long as $k$ is not too large when compared with $n.$

There is another result of this flavor by Templery and Haselgrove but this result is quite complex so I won't state it here.

References:

Erdos and Lehner, The Distribution of the Number of Summands in the Partitions of a Positive Integer

Templery and Haselgrove, Asymptotice Formulae in the Theory of Partitions

share|improve this answer

Using the recursion that yoyo mentioned, we can derive a similar formula as I mentioned in the answer to your previous question. That is, we can simply adjoin another variable $s$ to the formula $P(n,k)$ that keeps track of the number of addends used so far in making up the partition.

Let $R(n,k,s)$ denote the number of partitions of $n$ that use integers greater than or equal to $k$, and have exactly $s$ addends.

We find the following recursion (by conditioning on whether the smallest term in the partition is $k$ or strictly larger than $k$:

$$ R(n,k,s) = \begin{cases} R(n-k,k,s-1)+R(n,k+1,s) & \text{if $s>=1$,} \ 0 & \text{if $ks > n$,} \ 1 & \text{if $s=1, n>=k$.} \ \end{cases} $$

I checked the above formula to compute $R(13,3,3)$, which gives the correct answer $4$.

share|improve this answer
    
Can someone (moderators?) please edit the above formula? I intended it to be defined in a piecewise manner, but \begin{cases} ... \end{cases} seems to be clobbered by MathJax. –  quantumelixir Apr 17 '11 at 16:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.