# Correlation of an approximation over a random permutation

I read a paper of linear cryptanalysis that is J.Daemen et al's Probability distribution of correlation and differentials in block cipher.

In this paper's lemma 8's proof, I can't understand this formula (page.13).

The number of balanced Boolean functions $$g(a)$$ for a given value of $$x$$ is :

$${{2^{n-1}} \choose {2^{n-2}+x}} {{2^{n-1}} \choose {2^{n-2}-x}} = {{2^{n-1}} \choose {2^{n-2}+x}}^2$$ and

If we divide this by the total number of balanced Boolean functions,..."

Please, tell me how this formula is derived.

So $$x$$ measures the departure from balance in the left half of the truth table, say it is the excess number of 1's in the left half of length $$2^{n-1}$$. By the definition of binomial coefficients there are $$\binom{2^{n-1}}{2^{n-2}+x}$$ such vectors. This is the first factor. The second factor is the count of vectors missing $$x$$ 1's, since the overall truth table is balanced.
Using $$\binom{a}{b}=\binom{a}{a-b}$$ completes the argument.