Skip to main content
1 of 2
Lucia
  • 43.7k
  • 6
  • 193
  • 218

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. This is 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). $$ 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). $$

Lucia
  • 43.7k
  • 6
  • 193
  • 218