Partition with minimum size of parts

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

\begin{align*} [x^4]&(1+x^2+x^4)(1+x^3)(1+x^4)\tag{2}\\ &\qquad=[x^4](1+x^2+x^4)(1+x^3+x^4)\tag{3}\\ &\qquad=[x^4](1+x^2+x^3+2x^4)\tag{4}\\ &\qquad=2 \end{align*} and we are finished.

Comment:

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

Answer 4

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.