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.