# Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$.

A napkin calculation suggests that $\{1,\ldots,n\}$ has about $n^2\log n$ many subsets that form arithmetic progressions, i.e., are evenly spaced''. Example: the only subsets of $\{1,2,3,4\}$ that are not evenly spaced are $\{1,2,4\}$ and $\{1,3,4\}$.

It seems harder to determine the number $A_n$ of partitions of $\{1,\ldots,n\}$ in which each block is evenly spaced. So my question is: what can be said about the growth rate of $A_n$?

-
I suggest to add this statistic to findstat.org –  Per Alexandersson Feb 17 '14 at 8:42
Here are some values for $A_n$ computed with a modern napkin: $1,2,5,13,37,111,359,1211$, which is oeis.org/A053732 (though the page doesn't contain any new information). @PerAlexandersson It's not really a statistic on a combinatorial collection, is it? –  Christian Stump Feb 17 '14 at 9:18
blocks of size 1 and 2 count as arithmetic progressions? –  Gerry Myerson Feb 17 '14 at 10:57
@GerryMyerson yes –  Bjørn Kjos-Hanssen Feb 17 '14 at 14:33
@ChristianStump: This is a subset of set partitions right? So, one can have a statistic that is 1 if all blocks are arithmetic progressions and 0 otherwise. –  Per Alexandersson Feb 17 '14 at 15:59

I will prove that $$A_n = \Big(\frac{n}{e}\Big)^{n/2} \exp(O(\sqrt{n})).$$ With more effort, one could probably even get an asymptotic formula. Moreover the argument suggests that a typical such set partition consists of about $C_1\sqrt{n}$ singleton sets, about $C_2\sqrt{n}$ sets of size $3$, a bounded number of sets of size four, no sets of size five or more, and the rest comprising of doubleton sets. (See the Additional Remarks section for a rough sketch of what I have in mind.) This is in contrast to a typical set partition where the sets tend to have size about $\log n$.

Let $C(n)$ denote the number of ways of partitioning an $n$-element set into doubleton sets. Clearly $C(n)=0$ if $n$ is odd and $C(n)$ equals $(n-1)\cdot (n-3)\cdot \ldots \cdot 1$ if $n$ is even. Using Stirling's formula $C(n)\sim \sqrt{2} (n/e)^{n/2}$ if $n$ is even.

Clearly $A_n$ is at least the number of ways of partitioning $\{1,\ldots, n\}$ into just singleton and doubleton sets. Note that $k$ singleton sets may be chosen in $\binom{n}{k}$ ways, and the remaining doubleton sets in $C(n-k)$ ways (and we may assume that $n$ and $k$ have the same parity). Thus $$A_n \ge \sum_{k} \binom{n}{k} C(n-k)$$ and a calculation using our asymptotic for $C(n-k)$ shows that this is $$\sim C \Big( \frac{n}{e}\Big)^{n/2} e^{\sqrt{n}},$$ for some positive constant $C$. This gives the lower bound part of the claimed behavior for $A_n$.

Now let's turn to the upper bound. Suppose that the set partition has $k_1$ singletons, $k_3$ sets of size $3$, $k_4$ sets of size $4$ and so on. Note that $k_1+3k_3+4k_4+\ldots$ must be at most $n$ and have the same parity as $n$. The number of choices for the $k_1$ singletons is $\binom{n}{k_1} \le n^{k_1}/k_1!$. Consider now the choices for the three element sets. There are at most $n^2/4$ ways of picking a three term progression in $\{1,\ldots, n\}$ (pick the starting point $a$ and then there are at most $(n-a)/2$ choices for the common difference $d$), and therefore the number of ways of picking $k_3$ three term sets is at most $(n^2/2)^{k_3}/k_3!$. Similarly the number of $j$-term progressions in $\{1,\ldots, n\}$ is at most $n^2/(2(j-1))$, and so the number of ways of picking $k_j$ sets with $j$ elements is at most $(n^2/(2(j-1)))^{k_j}/k_j!$. Thus we find that $$A_n \le \sum_{k_1, k_3, k_4, \ldots} \frac{n^{k_1}}{k_1!} \prod_{j\ge 3} \frac{1}{k_j!} \Big(\frac{n^2}{2(j-1)}\Big)^{k_j} C(n-k_1-3k_3-\ldots).$$ Now we use above that $C(n-k_1-3k_3 -\ldots) = O((n/e)^{(n-k_1-3k_3-\ldots)/2})$. Thus we get that $$A_n = O\Big( \Big(\frac{n}{e}\Big)^{n/2} \sum_{k_1, k_3, k_4, \ldots} \frac{(en)^{k_1/2}}{k_1!} \prod_{j\ge 3} \frac{1}{k_j!} \Big( \frac{e^{j/2}n^{2-j/2}}{2(j-1)}\Big)^{k_j} \Big). \tag{1}$$ Simply extend the sums over $k_1$, $k_3$, $\ldots$ to run over all non-negative integers. We find that $$A_n = O\Big( \Big(\frac{n}{e}\Big)^{n/2} \exp\Big( \sqrt{en} + \sum_{j\ge 3} \frac{e^{j/2}n^{2-j/2}}{2(j-1)}\Big) \Big) = O\Big( \Big(\frac{n}{e}\Big)^{n/2} \exp(O(\sqrt{n}))\Big).$$

Additional remarks. If one inspects the upper bound argument above, then one can show that terms with $k_1+3k_3+4k_4+\ldots \ge 100\sqrt{n}$ contribute an amount $\le (n/e)^{n/2}$. To see this, multiply the bound in (1) by $\exp((k_1+3k_3+\ldots)-100\sqrt{n})$ which is $\ge 1$ for such terms, and then extend $k_j$ to all natural numbers and bound as before. So certainly the bulk of the contribution will come from terms with $k_1+3k_3+\ldots \le 100\sqrt{n}$, so that already most sets are doubletons. In this range we can replace $C(n-k_1-3k_3-\ldots)$ by $\sim \sqrt{2} (n/e)^{n/2} n^{-(k_1+3k_3+\ldots)/2}$. This leads to a better bound in (1) with the $e^{k_1/2}$ and $e^{jk_j/2}$ terms removed. Now carrying out our argument gives the more precise bound $$A_n = O\Big( \Big(\frac{n}{e}\Big)^{n/2} \sum_{k_1,k_3,\ldots} \frac{n^{k_1/2}}{k_1!} \prod_{j\ge 3} \frac{1}{k_j!} \Big(\frac{n^{2-j/2}}{2(j-1)}\Big)^{k_j} \Big), \tag{2}$$ which leads to the sharper upper bound $$A_n = O\Big( \Big(\frac{n}{e}\Big)^{n/2} \exp\Big( \frac{5\sqrt{n}}4\Big)\Big). \tag{3}$$ I expect this bound to be tight, and that $A_n$ is really asymptotic to some constant times this expression (reason below). Granting this for the moment, what (2) tells us is that we should view $k_1$ as being roughly speaking Poisson with parameter $\sqrt{n}$, $k_3$ is Poisson with parameter $\sqrt{n}/4$, $k_4$ is Poisson with parameter $1/6$, and note that $k_5$ and above are Poisson with a very small parameter so that usually they are likely to be zero. This is the reasoning behind my comment on the structure of a typical set partition of the type considered here -- $k_1$ is likely to be about $\sqrt{n}$, $k_3$ of size $\sqrt{n}/4$, $k_4$ of constant size, and $k_5$ and above are likely to be zero.

Lastly let me explain why there should be a corresponding lower bound of the same size as in (3) (this wouldn't be too hard to prove; a precise asymptotic would be more challenging). In the upper bound argument we just sampled arithmetic progressions of length $j$ in $\{1,\ldots,n\}$ repeatedly, ignoring the fact that the progressions we pick should be disjoint. The point is that if we pick only a small number of progressions (which is true when $k_1+3k_3+\ldots \le 100\sqrt{n}$), then there is a positive probability that sampling repeatedly will lead to a choice with disjoint sets. In other words, there is a lower bound of the same shape as (2) in this range of parameters, and that is enough to give the lower bound (3). Another way to say this is that if we just consider set partitions into blocks of size $1$, $2$ or $3$ (and these being APs) then we'd get about the quantity in (3) -- first pick about $\sqrt{n}/4$ disjoint three term progressions, then pick about $\sqrt{n}$ singleton sets, and then use doubletons for the rest.

-
@BjørnKjos-Hanssen: I added some more remarks on this. Please do let me know if something is unclear. –  Lucia Feb 19 '14 at 1:04
Lucia, thanks, that helps. Great answer. –  Bjørn Kjos-Hanssen Feb 19 '14 at 6:31