Problem from an old exam:
A full binary tree of height $n$ has $2^n-1$ vertices. We randomly insert all numbers $1, \ldots, 2^n-1$ into it (each permutation is equally likely). An error is defined as a pair of vertices $(v, w)$ such that $v$ is the ancestor of $w$, but the value in $v$ is smaller than the value in $w$ (we want a max-heap). Let $X$ be a random variable indicating the number of errors.
Find the generating function of the probability distribution of the random variable $X, g_X(t)$. It is sufficient to give the answer in the form of a product of expressions in a compact form.
Where should I start solving this problem? I have seen similar problem before and it was solved using recurrence relation. Also, Shouldn't $n$ be specified in order to be able to find that generating function?
Let $Q_n$ be the generating function in $x$ that we seek where the exponent gives the number of inversions in a full binary heap on $2^n-1$ nodes. We have $Q_1 = 1$. On the other hand for the recursion we must first choose the top node from among the $2^n-1$ possibilities and choose the labels that go onto the left subtree for ${2^n-2\choose 2^{n-1}-1}$ possibilities, with the remaining labels going to the right subtree. With the top node $k$ it will clearly produce $2^n-1-k$ additional inversions as we are asking for a max-heap. We label the subtrees respecting the ordering of nodes in the source trees, same as when we do the labeling of the cartesian product of two exponential generating functions for combinatorial classes. Here we have an OGF however. This gives the recurrence
$$Q_n = \sum_{k=1}^{2^n-1} x^{2^n-1-k} {2^n-2\choose 2^{n-1}-1} Q_{n-1}^2$$
or alternatively
$$Q_n = Q_{n-1}^2 {2^n-2\choose 2^{n-1}-1} \sum_{k=0}^{2^n-2} x^{k}.$$
E.g. we have
$$Q_3 = 80 x^{10}+240 x^{9}+480 x^{8}+640 x^{7}+720 x^{6} \\ +720 x^{5}+720 x^{4}+640 x^{3}+480 x^{2}+240 x +80.$$
Look it up in the OEIS to get a pointer to OEIS A306393, where more data awaits.
Remark. We can actually unroll the recursion to get
$$Q_n = \prod_{q=0}^{n-1} \left[\frac{1-x^{2^{n-q}-1}}{1-x}\right]^{2^q} \prod_{q=0}^{n-1} {2^{n-q}-2\choose 2^{n-q-1}-1}^{2^q}$$
or
$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{(1-x)^{2^n-1}} \prod_{q=0}^{n-1} {2^{n-q}-2\choose 2^{n-q-1}-1}^{2^q} \prod_{q=0}^{n-1} \left[1-x^{2^{n-q}-1}\right]^{2^q}.}$$
Observation. We get for the average number of inversions that it is given by
$$\frac{1}{(2^n-1)!} \prod_{q=0}^{n-1} {2^{n-q}-2\choose 2^{n-q-1}-1}^{2^q} \left. \prod_{q=0}^{n-1} [1+\cdots+x^{2^{n-q}-2}]^{2^q} \\ \times \sum_{q=0}^{n-1} 2^q \frac{1+2x+3x^2+\cdots+(2^{n-q}-2)x^{2^{n-q}-3}} {1+\cdots+x^{2^{n-q}-2}} \right|_{x=1} \\ = \frac{1}{(2^n-1)!} \prod_{q=0}^{n-1} {2^{n-q}-2\choose 2^{n-q-1}-1}^{2^q} \prod_{q=0}^{n-1} [2^{n-q}-1]^{2^q} \\ \times \sum_{q=0}^{n-1} 2^{q-1} \frac{(2^{n-q}-2)(2^{n-q}-1)}{2^{n-q}-1} \\ = \frac{1}{(2^n-1)!} \prod_{q=0}^{n-1} {2^{n-q}-2\choose 2^{n-q-1}-1}^{2^q} \prod_{q=0}^{n-1} [2^{n-q}-1]^{2^q} \\ \times \sum_{q=0}^{n-1} (2^{n-1}-2^q).$$
We have for the product terms
$$\frac{1}{(2^n-1)!} \prod_{q=1}^{n} \frac{(2^{n+1-q}-2)!^{2^{q-1}}}{(2^{n-q}-1)!^{2^{q}}} \prod_{q=0}^{n-1} [2^{n-q}-1]^{2^q} \\ = \frac{1}{(2^n-2)!} \prod_{q=1}^{n} \frac{(2^{n+1-q}-2)!^{2^{q-1}}}{(2^{n-q}-1)!^{2^{q}}} \prod_{q=1}^{n-1} [2^{n-q}-1]^{2^q} \\ = \frac{1}{(2^n-2)!} \prod_{q=1}^{n-1} \frac{(2^{n+1-q}-2)!^{2^{q-1}}}{(2^{n-q}-1)!^{2^{q}}} \prod_{q=1}^{n-1} [2^{n-q}-1]^{2^q} \\ = \frac{1}{(2^n-2)!} \prod_{q=1}^{n-1} \frac{(2^{n-(q-1)}-2)!^{2^{q-1}}}{(2^{n-q}-2)!^{2^{q}}} \\ = \frac{1}{(2^n-2)!} \prod_{q=1}^{n-1} \frac{(2^{q+1}-2)!^{2^{n-q-1}}}{(2^{q}-2)!^{2^{n-q}}} = 1.$$
This leaves just the sum term, producing
$$2^{n-1} \times n - (2^n-1)$$
or
$$\bbox[5px,border:2px solid #00A000]{ 2^{n-1} \times (n-2) + 1.}$$
In terms of the number $m$ of nodes we get on average $O(m \times \log m)$ inversions.