"Spread-Out" Partitions 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.
 A: 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.$
A: 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\\
$$
A: 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$.
