# Partition with minimum size of parts

In how many ways can we partition a number $N$? The answer is given by the partition function $p(N)$. So for instance, the partitions of the number $4$ are: \begin{equation} 4; ~~~ 3+1;~~~ 2+2;~~~ 2+1+1;~~~1+1+1+1 \end{equation} and hence $p(4) = 5$. How is this modified if I require each part to be at least of some size $k$? So for instance, if I required that each part must be at least of size $k=2$, the valid partitions of $4$ would be reduced to \begin{equation} 4; ~~~ 2+2. \end{equation} How is this formalized? And is there a systematic way of enumerating all possibilities?

• Partitions of $n$ with $r$ parts and minimum part size $k$ are in bijection with partitions of $n-r(k-1)$ and $r$ parts. There are known formulas for the latter. – rogerl Dec 23 '16 at 15:19
• Can the same techniques be applied to solve this problem? math.stackexchange.com/questions/3238496/… – Dunkel May 29 '19 at 19:25

Define function that you ask for as $p^k(N)$. Consider "partial partition" $p_m(N)$ as number of partitions of $N$ on exactly $m$ positive integers. Partition site on Wikipedia has some information about it. For example:

• $p_2(2N)=N$, because $2N=1+(2N-1)=2+(N-2)=..=N+N$
• $p_3(6)=3$; $\ \ (1,1,4);\ \ (1,2,3);\ \ (2,2,2)$
• $p_m(N)=0\ \$ when $m>N$
• assumptions: $p_m(N)=0\ \$ when $N<0$, with the exception of $p_0(0) = 1$.

Then by definition we get $p(N)=\sum_{i=1}^{N}p_i(N)$.

It is convenient to represent any partition of N as nondecreasing sequence of positive integers that sums up to $N$ ("no order at all" is the same as "one fixed order").

Lets try to compute "partial partition" $p_m^k(N), \ k\geqslant 1$ of $N$ on exactly $m$ summands with each summand not less than $k$. First of all if $m*k>N$ then $p_m^k(N)=0$. Note that $p_m^1(N)=p_m(N)$. Assume that $m*k\leq N$. Imagine constant sequence $(a_i)_{i=1}^{m}$ with $a_i=k-1$ for all $i$. If we add (position-wise) some nondecreasing sequence of positive integers $(b_i)_{i=1}^{m}$ that sums up to $N-m*(k-1)$ (in other words any $m$-element partition of the number $r=N-m*(k-1)$), then resulting sequence $(c_i)_{i=1}^{m},\ \ c_i=a_i+b_i$ will be nondecreasing, $c_i\geqslant k$ for all $i$ and $\sum_{i=1}^{m}c_i=N$. Therefore sequence $(c_i)_{i=1}^{m}$ is $m$-element partition of $N$. Notice that above reasoning fixes one-to-one correspondence between $m$-element partition of $N-m*(k-1)$, and $m$-element partition of $N$ with summands $\geqslant k$. Thus $p_m^k(N)=p_m(N-m*(k-1))$.

By definition of $p_m^k(N)$ equation $p^k(N)=\sum_{i=1}^{N}p_i^k(N)$ is true. Now your function can be expressed as sum of $p_m(N)$: $$\sum_{i=1}^{N}p_i(N-i*(k-1))$$ wchich is pretty nice, because there is recurrence formula: $p_m(n) = p_m(n − m) + p_{m − 1}(n − 1)$ among other representations of that function.

For each partition of $n$ into no more than $p$ parts, we want a non-increasing sequence, $\{s_k\}_{k=1}^p$ summing to $n$. That is $$\overset{\substack{\text{smallest}\\\text{number}\\\downarrow}}{s_p}+s_{p-1}+s_{p-2}+\cdots+\overset{\substack{\text{largest}\\\text{number}\\\downarrow}}{s_1}=n\tag{1}$$ To make sure the sequence is non-increasing, we can consider the non-negative sequence $a_k=s_k-s_{k+1}$, where we set $s_{p+1}=0$. Then we get \begin{align} n &=\sum_{k=1}^ps_k\\ &=\sum_{k=1}^p\sum_{j=k}^p(s_j-s_{j+1})\\ &=\sum_{j=1}^p\sum_{k=1}^ja_j\\ &=\sum_{j=1}^pja_j\tag{2} \end{align} Thus, the number of non-increasing sequences $\{s_k\}_{k=1}^p$ that sum to $n$, is equal to the number of non-negative sequences $\{a_k\}_{k=1}^p$ so that $$\sum_{k=1}^pka_k=n\tag{3}$$ The generating function for the number of ways to partition $n$ into no more than $p$ parts, that is, the generating function for the number of non-negative sequences that satisfy $(3)$, is \begin{align} &\prod_{k=1}^p\left(1+x^k+x^{2k}+x^{3k}+\cdots\right)\\ &=\prod_{k=1}^p\frac1{1-x^k}\tag{4} \end{align} Thus, the generating function for partitioning into exactly $p$ parts is \begin{align} \prod_{k=1}^p\frac1{1-x^k}-\prod_{k=1}^{p-1}\frac1{1-x^k} &=\left(\frac1{1-x^p}-1\right)\prod_{k=1}^{p-1}\frac1{1-x^k}\\ &=\prod_{k=1}^p\frac{x}{1-x^k}\tag{5} \end{align} Noting that the generating function for the number of partitions of $n$ into $p$ parts with at least $m\ge1$ in each part is $x^{p(m-1)}$ times $(5)$. That is, the generating function for how many ways to partition $n$ into $p$ parts with at least $m$ in each part is $$\bbox[5px,border:2px solid #C0A000]{\prod_{k=1}^p\frac{x^m}{1-x^k}}\tag{6}$$ For $m=0$, $(6)$ becomes $(4)$, so $(6)$ encompasses all $m\ge0$.

Another technique is based upon generating functions. We encode the summands $j$ as powers of $x$ and the coefficient of $x^j$ provides the number of contributions of the summand $j$.

In the example with $N=4$ the number of partitions $p(4)$ is

\begin{align*} p(4)&=[x^4](x^0+x^1+x^2+x^3+x^4)(x^0+x^2+x^4)(x^0+x^3)(x^0+x^4)\\ &=[x^4](1+x+x^2+x^3+x^4)(1+x^2+x^4)(1+x^3)(1+x^4) \tag{1} \end{align*} Here we use the coefficient of operator $[x^j]$ to denote the coefficient of $x^j$ in a series. There are four factors in (1) indicating that the numbers $1,2,3$ and $4$ are the building blocks of a partition of $4$. The first factor in (1) tells us we can use the number $1$ zero or once or twice or up to four times, whereas e.g. the number $3$ can only be used zero or one time.

Now we want to analyse restricted partitions having smallest summand $k=2$. This means we are looking for

• In (2) we take contributions only from $k=2,3$ and $4$.
• In (3) we multiply the two right-most factors out and skip thereby all summands with powers greater then $4$ since they do nothing contribute to $[x^4]$.
• In (4) we multiply out and again skip summands with powers greater than four. We observe, the coefficient of $x^4$ is $2$ and we are done.
There is no easy closed formula for $p(n)$, so it should not be surprising that there is no formula either when a minimum size for the parts is imposed.
However both can be easily described using generating functions. For $p(n)$ this is the well known formula $$\sum_{n\in\Bbb N}p(n)X^n = \prod_{m=1}^\infty\frac1{1-X^m}$$ The foactor on the right for $m$ represents the possibility to choose any number of parts equal to $m$ in the partition. So if you want to restrict the parts to be at least $k$, it suffices to start the product at $m=k$: $$\sum_{n\in\Bbb N}p_{\geq k}(n)X^n = \prod_{m=k}^\infty\frac1{1-X^m}$$ One can incorporate more general conditions on the size of parts by varying the factors in the product, as you can find in the Wikipedia article on partitions.