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.


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

| cite | improve this answer | |
  • $\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$ – George Robinson Jun 25 '19 at 16:35
  • $\begingroup$ This answer addresses the question as it was when I started writing the answer. $\endgroup$ – Peter Taylor Jun 25 '19 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 }}} $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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