Let $P(n,k,m,z)$ be the number of partitions, that a positive integer $n$ can be partitioned into when each partition has exactly $k$ parts and when all of these parts are $\leq z$ and $\ge m$.

For example: $P(10,3,1,4) = 2$,
...because only two such triplets are possible: {4,4,2}, {4,3,3}.

Q) Is there a closed form or an asymptotic solution for $P(n,k,m,z)$, when $ k \leq n \leq kz$ and $ n \geq km$ ?

The answer in that post presents a beautiful idea to calculate the number of unrestricted integer partitions. It is based on:

  • The generating function: $\sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)}$
    combined with the:
  • Euler's Pentagonal theorem: $\prod_{n=1}^{\infty}\left(1-x^{n}\right)=\sum_{k=-\infty}^{\infty}\left(-1\right)^{k}x^{k\left(3k-1\right)/2}$

How can it be modified to calculate the number of integer partitions with the triple restriction by $k,m,z$ ?

I have seen similar questions about the number of integer partitions with 1 restriction, e.g. number of parts in partition OR a restriction on values of the parts ...but never BOTH.
Please consider that before marking this question as a duplicate.


2 Answers 2


Let's define some $q$-series notation: $(a;q)_n = \prod_{i=0}^{n-1} (1 - aq^i)$ with shorthand notation $(q)_n = (q;q)_n$. E.g. the left-hand side of Euler's pentagonal theorem as stated in the question is $(x)_\infty$.

Now, $$P(n,k,m) = [x^n z^k] \prod_{i=1}^m \frac{1}{1 - x^i z} = [x^n z^k] \frac{\prod_{i=m}^\infty (1 - x^{i+1} z)}{\prod_{i=0}^\infty (1 - x^{i+1} z)} = [x^n z^k] \frac{(x^{m+1}z;x)_\infty}{(xz;x)_\infty}$$

There are a couple of theorems due to Euler: $$(-x;q)_\infty = \sum_{k=0}^\infty q^{k(k-1)/2}(q)_k^{-1} x^k \\ (-x;q)_\infty^{-1} = \sum_{k=0}^\infty (-1)^k (q)_k^{-1} x^k$$

Then $$(x^{m+1}z;x)_\infty(xz;x)_\infty^{-1} = \left(\sum_{k=0}^\infty x^{k(k-1)/2}(x)_k^{-1} (-x^{m+1}z)^k\right) \left(\sum_{k=0}^\infty (-1)^k (x)_k^{-1} (-xz)^k\right) \\ = \left(\sum_{j=0}^\infty (-1)^j x^{j(j+2m+1)/2}(x)_j^{-1} z^j\right) \left(\sum_{k=0}^\infty (x)_k^{-1} x^k z^k\right) \\ = \sum_{j=0}^\infty \sum_{k=0}^\infty \frac{(-1)^j x^{j(j+2m+1)/2+k} z^{j+k}}{(x)_j (x)_k}$$

In particular, $$P(n,k,m) = [x^n] \sum_{j=0}^\infty \frac{(-1)^j x^{j(j+2m-1)/2+k}}{(x)_j (x)_{k-j}}$$

Note that if $P'(n,m)$ counts the partitions of $n$ into parts of at most $m$ then $$P'(n,m) = [x^n] \prod_{i=1}^m \frac{1}{1-x^i} = [x^n] (x)_m^{-1}$$ so $$P(n,k,m) = \sum_{a=0}^\infty \sum_{b=0}^\infty \sum_{j=0}^\infty (-1)^j P'(a,j) P'(b,k-j) [n-k-a-b=j(j+2m-1)/2]\\ = \sum_{a=0}^\infty \sum_{b=0}^\infty \sum_{j \in \frac{1-2m\pm\sqrt{4m^2-4m+1+8(n-k-a-b)}}{2}} (-1)^j P'(a,j) P'(b,k-j)$$

It's not quite as elegant as the pentagonal theorem...

  • $\begingroup$ Since parts p must be $m \leq p \leq z $, then the statement "$P'(n,m)$ counts the partitions of $n$ into parts of at most $m$" seems confusing. I think it should be: "...into parts of at most $z$" $\endgroup$ Jun 25, 2019 at 16:35
  • $\begingroup$ This answer addresses the question as it was when I started writing the answer. $\endgroup$ Jun 25, 2019 at 17:13

I do not see a way to get a o.g.f in the single variable $x$.
But it is possible to construct a 2D o.g.f. as

$$ P(n,k,m,z) = \left[ {x^{\,n} y^{\,k} } \right]\prod\limits_{m \le \,j\, \le \,z} {{1 \over {1 - y\,x^j }}} $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .