# Fair partitioning of a set - Weighted sums of Bernoullis

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.)

• What is RMS? $\,$ – James Martin Jul 3 '19 at 7:41
• Dear James, this is a french journal specialized in discussing problems that may be be adressed by undergrad (well, "prepa") students. Some stuff you may like there. No version on-line though. rms-math.com/… – Olivier Jul 3 '19 at 8:16
• These are counts of doubly-restricted partitions. Clearly you need $n$ to be even, say $2m$. This count then becomes the number of partitions of $m(4m+1)$ into $2m$ distinct positive parts each no more than $4m$, which is the number of partitions of $2m^2$ into $2m$ non-negative parts (or up to $2m$ positive parts) each no more than $2m$. – Henry Jul 7 '19 at 9:41
• The numbers are of such partitions are the values of OEIS A029895 when $n$ is even and that has the $\frac{\sqrt 3}{\pi}\frac{4^n}{n^2}$ expression and suggests $\frac{\sqrt 3}{\pi}\frac{4^n}{n^2+\frac35 n + \frac15}$ may be closer. Any example has a duplicate in the sense that $1+4=2+3$ is essentially the same as $2+3=1+4$, so if you halve the number then you get OEIS A168238. – Henry Jul 7 '19 at 10:05
• @Olivier subtract $2m$ from the largest part, $2m-1$ from the second largest, ... $2$ from the second smallest, and $1$ from the smallest part, at the same time as subtracting $\frac{2m(2m+1)}{2}$ from the total – Henry Jul 7 '19 at 15:06

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

• Txs Yuval for the nice "smoothing" trick, this is precisely what I was hoping for when posting the question. – Olivier Jul 3 '19 at 15:28
• This is incredibly nice. The proof by Zhou hides a substantial amount of complex analysis which is all bypassed by such a simple idea with a very simple criteria to apply. – Synia Jul 3 '19 at 16:03

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}.$$

• Great ! I also tried with the q-binomial theorem but I was stuck midway (basically when trying to extract the coefficient of the q-binomial coefficient). Very helpful indeed, txs. – Olivier Jul 2 '19 at 14:56