Fair partitioning of a set - Weighted sums of Bernoullis

Question

For $n$ an integer, let $a_n$ be the number of ways in which one may partition the set $\{1, \ldots, 2n \}$ in two parts with:

• the same number of elements: $n$
• and the same sum: $2n(2n+1)/4$.

Find an equivalent of $a_n$.

—

Put in probabilistic terms: let $(B_i)_{1\le i \le 2n}$ be independent Bernoulli($1/2$) random variables. Find an equivalent of the probability:

$b_n = \mathbf P\left[\sum_{i=1}^{2n} B_i =n , \sum_{i=1}^{2n} i B_i = 2n(2n+1)/4\right]$

The two quantities are related by $a_n= 4^{-n} b_n$.

—

Edit: $n$ has to be even for the above quantities to be non-zero; otherwise the half-sum $2n(2n+1)/4$ is not an integer.

—

The (numerically verified) conjecture is that, for some constant $c$, and for even $n$:

$$a_n \sim c \cdot \frac{4^n}{n^2}$$

Using bravely local central limit theorem (which amounts to assume the two random variables $(\sum_{i=1}^{2n} B_i, \sum_{i=1}^{2n}i B_i)$ form a gaussian vector), computing the mean vector and covariance matrix of that vector - the two random variables are indeed correlated in the limit - and taking into account aperiodicity (edit: no need!), one might even guess that

$c= \frac{\sqrt{3}}{\pi}$

—

How to make this rigorous?

—

(The question was raised in RMS as R772, where the conjecture is also stated; I feel there is some interest to share this with a broader audience.)

Answer 1

The answer given above by Zhou is excellent, but some (including the OP) may be interested in rigorizing the Local CLT approach he suggested. This can be done using characteristic functions. There are several sources developing this in the needed generality including Petrov's book "sums of independent random variables" and the paper "Local Limit Theorems for Lattice Random Variables" by A. B. Mukhin https://doi.org/10.1137/1136086

My favorite approach, when it can be applied, is that of
"An elementary proof of the local central limit theorem B Davis, D McDonald - Journal of Theoretical Probability, 1995 " (see http://www.stat.purdue.edu/research/technical_reports/pdfs/1993/tr93-41.pdf )

To apply Theorem 3 there, one needs to show a smoothness property found in line 2 of the statement. This can be achieved by regrouping the variables. Write $Y_i=(B_i,iB_i)$. For $1 \le i < n/9$, say, let $X_i=Y_{2i}+Y_{2i+1}$, and observe that changing the vector $(B_{2i},B_{2i+1})$ from $(1,0)$ to $(0,1)$ increases $X_i$ by the second standard basis vector $e_2$.

Then consider the sum of $Z_i=Y_{i}+Y_{2i}+Y_{3i}$ over $2n/9 \le i < n/3$. Changing the vector $(B_{i},B_{2i},B_{3i})$ from $(0,0,1)$ to $(1,1,0)$ increases $Z_i$ by the first basis vector $e_1$. This establishes the smoothness requirement of Theorem 3. Note that we are really using the triangular array version of Theorem 3. The proof is completely elementary, it is based on the idea that if we add an approximately Gaussian variable to one of the same magnitude that satisfies a local CLT, then the resulting sum satisfies the Local CLT. For further explanation and applications of this idea, see Theorem 2.1 in Penrose, Mathew, and Yuval Peres. "Local central limit theorems in stochastic geometry." Electronic Journal of Probability 16 (2011): 2509-2544.

http://emis.ams.org/journals/EJP-ECP/_ejpecp/include/getdoc9762.pdf?id=6355&article=2306&mode=pdf

Answer 2

The conjecture is ture for even integer $n\rightarrow +\infty$. In fact, from the theory of integer partitions and Cauchy Binomial Theorem, it is easy to find that if $n\in 2\mathbb{N}$ then \begin{align} a_{n}&=\left[\zeta^{n}q^{\frac{2n(2n+1)}{4}}\right]\prod_{k=1}^{2n}(1+\zeta q^k)\\ &=\left[\zeta^{n}q^{n(2n+1)/2}\right]\sum_{k=0}^{2n}\zeta^kq^{\frac{k(k+1)}{2}}\frac{(q)_{2n}}{(q)_k(q)_{2n-k}}\\ &=\left[q^{n^2/2}\right]\frac{(q)_{2n}}{(q)_{n}^2}, \end{align} where $$(q)_k:=\prod_{1\le j\le k}(1-q^j),~~ k\in\mathbb{Z}_{\ge 0}.$$

By [L. Takács, Some asymptotic formulas for lattice paths, JSPI,1986] or [G. Almkvist, G.E. Andrews, A Hardy-Ramanujan formula for restricted partitions, JNT, 1991], or Equation (1.4) in [Tiefeng Jiang, Ke Wang, A generalized Hardy-Ramanujan formula for the number of restricted integer partitions, JNT,2019], we have

$$a_n\sim \binom{2n}{n}\sqrt{\frac{6}{\pi n^2(2n+1)}}\sim \frac{4^n}{\sqrt{\pi n}}\sqrt{\frac{3}{\pi n^{3}}}=\frac{\sqrt{3}}{\pi}\frac{4^n}{n^2}.$$