"Spread-Out" Partitions

Question

Firstly, the given definition of spread-out is

"A partition is said to be 'spread-out' if all the parts are distinct and no two parts are consecutive numbers."

I am trying to work out how many spread-out partitions of 21 are there into 4 parts? I believe the answer is 7, but I only achieved this by brute force, and hence wondering if there is a easier way and more general formula of working this out.

Answer 1

Let $f(n,k,m)$ be the number of spread-out partitions of $n$ into $k$ distinct parts of size at most $m$. By conditioning on whether part $m$ appears, we find that $$f(n,k,m) = f(n-m,k-1,\min(m-2,n-m)) + f(n,k,m-1)$$ with obvious boundary conditions. We want to compute $f(21,4,21)$, which turns out to be $6$. The corresponding partitions are $$ 12+5+3+1\\ 11+6+3+1\\ 10+7+3+1\\ 10+6+4+1\\ 9+7+4+1\\ 9+6+4+2\\ $$

Answer 2

For admissible partitions of $n$ into $k$ elements we choose the first element and a sequence of $k-1$ differences between consecutive elements, with these being at least two. The first element contributes to all $k$ elements. The first difference contributes to $k-1$ values, the second to $k-2$ and so on. This yields the OGF

$$G_k(z) = \frac{z^k}{1-z^k} \times \prod_{q=1}^{k-1} \frac{z^{2q}}{1-z^q} = z^{k^2} \prod_{q=1}^k \frac{1}{1-z^q}.$$

We are interested in $g_k(n) = [z^n] G_k(z).$ Differentiate to get

$$G'_k(z) = k^2 z^{k^2-1} \prod_{q=1}^k \frac{1}{1-z^q} + z^{k^2} \prod_{q=1}^k \frac{1}{1-z^q} \sum_{q=1}^k \frac{qz^{q-1}}{1-z^q}.$$

Extracting the coefficient on $[z^n]$ yields

$$(n+1) g_k(n+1) = k^2 g_k(n+1) + \sum_{q=1}^k q [z^{n+1-q}] \frac{1}{1-z^q} G_k(z) \\ = k^2 g_k(n+1) + \sum_{q=1}^k q \sum_{p=0}^{\lfloor (n+1)/q \rfloor -1} g_k(n+1-(p+1)q).$$

This gives the recurrence

$$g_k(n+1) = \frac{1}{n+1-k^2} \sum_{q=1}^k q \sum_{p=0}^{\lfloor (n+1)/q \rfloor -1} g_k(n+1-(p+1)q)$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ g_k(n) = \frac{1}{n-k^2} \sum_{q=1}^k q \sum_{p=1}^{\lfloor n/q \rfloor} g_k(n-pq).}$$

with the boundary conditions being $g_k(n) = 0$ when $n\lt k^2$ and $g_k(k^2) = 1.$

This will indeed produce $g_4(21) = 6.$

Answer 3

Wanted to add some to the answers of Reidel and Pratt from 18 January. These spread-out partitions are sometimes called 2-distinct partitions (where $d$-distinct means distinct parts with differences at least $d$). 2-distinct partitions are part of the first Rogers--Ramanujan identity (Schur also proved it independently): writing # for "number of," $$ \#\text{(2-distinct partitions of $n$)} = \#\text{(partitions of $n$ with all parts congruent to 1 or 4 modulo 5)}.$$ In terms of generating functions, this is $$ 1 + \sum_{m=1}^\infty \frac{q^{m^2}}{(1-q)(1-q^2)\cdots(1-q^m)} = \prod_{n=1}^\infty \frac{1}{(1-q^{5n-4})(1-q^{5n-1})}.$$ A great exposition on this is in the book Integer Partitions by George Andrews and Kimmo Eriksson (Cambridge, 2004), section 3.4, chapter 4, and section 5.6.

Your question of counting 2-distinct partitions of $n$ by number of parts leads to the triangle of numbers in the On-line Encyclopedia of Integer Sequences entry A268187. The description of partitions there is different, but connects to 2-distinct partitions in a way that preserves the number of parts. The row for $n=21$ is $1, 9, 19, 6$.