Partition an integer $n$ by limitation on size of the partition

Question

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$.

Answer 1

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.

Answer 2

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

Answer 3

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$.