5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – rogerl Dec 23 '16 at 15:19
  • $\begingroup$ Can the same techniques be applied to solve this problem? math.stackexchange.com/questions/3238496/… $\endgroup$ – Dunkel May 29 '19 at 19:25
1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.