TAOCP 7.2.2.1 Exercise 226
Let $a_1,\dots,a_{2n}$ be a Langford pairing, and define the reversed sequence by $a'_k = a_{2n+1-k}, \qquad 1 \le k \le 2n.$ For any function $f$, define $T_f = \sum_{k=1}^{2n} k\, f(a_k), \qquad T_f...
Section 7.2.2.1: Dancing Links
Exercise 226. [M30] Assume that $a_1 \ldots a_{2n}$ is a Langford pairing, and let $a'k = a{2n+1-k}$ so that $a'1 \ldots a'{2n}$ is the reverse of $a_1 \ldots a_{2n}$. Are there any obvious relations between the sums
$$\Sigma_1 = \textstyle\sum_{k=1}^{2n} k a_k, \quad \Sigma_2 = \textstyle\sum_{k=1}^{2n} k a_k^2, \quad \Sigma_3 = \textstyle\sum_{k=1}^{2n} k^2 a_k, \quad \Sigma_4 = \textstyle\sum_{k=1}^{2n} k^2 a_k^2$$
What about the analogous sums $S = \sum_{k=1}^{2n} k a_k^3$ and $S' = \sum_{k=1}^{2n} k(a_k^2)^2$?
Verified: yes
Solve time: 1m47s
Setup
Let $a_1,\dots,a_{2n}$ be a Langford pairing, and define the reversed sequence by
$a'k = a{2n+1-k}, \qquad 1 \le k \le 2n.$
For any function $f$, define
$T_f = \sum_{k=1}^{2n} k, f(a_k), \qquad T_f' = \sum_{k=1}^{2n} k, f(a'_k).$
Introduce the aggregate quantities
$A_r = \sum_{k=1}^{2n} a_k^r, \qquad r \in \mathbb{N},$
and the weighted sums
$\Sigma_r = \sum_{k=1}^{2n} k^r a_k, \qquad \Sigma_r^{(2)} = \sum_{k=1}^{2n} k^r a_k^2.$
The goal is to express the reversed sums in terms of the original sums.
Solution
1. Linear change of index
Start with
$\Sigma_1' = \sum_{k=1}^{2n} k, a'{k} = \sum{k=1}^{2n} k, a_{2n+1-k}.$
Set $j = 2n+1-k$, so $k = 2n+1-j$. Substitution yields
$\Sigma_1' = \sum_{j=1}^{2n} (2n+1-j)a_j.$
Expand the sum:
$\Sigma_1' = (2n+1)\sum_{j=1}^{2n} a_j - \sum_{j=1}^{2n} j a_j.$
Hence
$\Sigma_1' = (2n+1)A_1 - \Sigma_1.$
2. Quadratic weight with $a_k^2$
Similarly,
$\Sigma_2' = \sum_{k=1}^{2n} k, (a'k)^2 = \sum{k=1}^{2n} k, a_{2n+1-k}^2.$
With the same substitution,
$\Sigma_2' = \sum_{j=1}^{2n} (2n+1-j)a_j^2.$
Thus
$\Sigma_2' = (2n+1)\sum_{j=1}^{2n} a_j^2 - \sum_{j=1}^{2n} j a_j^2,$
so
$\Sigma_2' = (2n+1)A_2 - \Sigma_2^{(1)},$
where $\Sigma_2^{(1)} = \sum_{k=1}^{2n} k a_k^2$.
3. Quadratic weight with $k^2 a_k$
Compute
$\Sigma_3' = \sum_{k=1}^{2n} k^2 a'{k} = \sum{k=1}^{2n} k^2 a_{2n+1-k}.$
Substitute $k = 2n+1-j$:
$\Sigma_3' = \sum_{j=1}^{2n} (2n+1-j)^2 a_j.$
Expand the square:
$(2n+1-j)^2 = (2n+1)^2 - 2(2n+1)j + j^2.$
Insert into the sum:
$\Sigma_3' = (2n+1)^2 \sum_{j=1}^{2n} a_j - 2(2n+1)\sum_{j=1}^{2n} j a_j + \sum_{j=1}^{2n} j^2 a_j.$
Therefore
$\Sigma_3' = (2n+1)^2 A_1 - 2(2n+1)\Sigma_1 + \Sigma_3.$
4. Quadratic weight with $k^2 a_k^2$
Compute
$\Sigma_4' = \sum_{k=1}^{2n} k^2 (a'k)^2 = \sum{k=1}^{2n} k^2 a_{2n+1-k}^2.$
After substitution,
$\Sigma_4' = \sum_{j=1}^{2n} (2n+1-j)^2 a_j^2.$
Expanding as before,
$\Sigma_4' = (2n+1)^2 A_2 - 2(2n+1)\Sigma_2^{(1)} + \Sigma_4.$
5. Cubic and quartic analogues
Define
$S = \sum_{k=1}^{2n} k a_k^3, \qquad Q = \sum_{k=1}^{2n} k a_k^4.$
For the reversed sequence,
$S' = \sum_{k=1}^{2n} k (a'k)^3 = \sum{k=1}^{2n} k a_{2n+1-k}^3.$
Substitution gives
$S' = \sum_{j=1}^{2n} (2n+1-j)a_j^3,$
hence
$S' = (2n+1)\sum_{j=1}^{2n} a_j^3 - \sum_{j=1}^{2n} j a_j^3.$
Thus
$S' = (2n+1)A_3 - S.$
Similarly,
$Q' = \sum_{k=1}^{2n} k (a'k)^4 = \sum{k=1}^{2n} k a_{2n+1-k}^4,$
and substitution yields
$Q' = (2n+1)A_4 - Q.$
Verification
Each transformation uses the bijection $k \leftrightarrow j = 2n+1-k$, which permutes ${1,\dots,2n}$, preserving summation range.
Linear terms arise from expansion of $(2n+1-j)$, and quadratic terms arise from binomial expansion of $(2n+1-j)^2$. No cross-terms remain after collecting sums since each separates into $A_r$ or $\Sigma_r$ forms.
Each reversed expression reduces to a linear combination of original power-sums with coefficients determined solely by powers of $2n+1$.
Result
The reversal identities are
$\Sigma_1' = (2n+1)A_1 - \Sigma_1,$
$\Sigma_2' = (2n+1)A_2 - \sum_{k=1}^{2n} k a_k^2,$
$\Sigma_3' = (2n+1)^2 A_1 - 2(2n+1)\Sigma_1 + \Sigma_3,$
$\Sigma_4' = (2n+1)^2 A_2 - 2(2n+1)\sum_{k=1}^{2n} k a_k^2 + \Sigma_4,$
and for higher powers,
$S' = (2n+1)A_3 - S, \qquad Q' = (2n+1)A_4 - Q.$
This completes the solution. ∎