TAOCP 7.2.1.2 Exercise 104
Let S(a_1\ldots a_n)=\sum_{k=1}^n k a_k.
Section 7.2.1.2: Generating All Permutations
Exercise 104. ▶ [M22] [M22] A permutation a1 . . . an of {1, . . . , n} is well-balanced if n k=1 kak = n k=1 (n + 1 −k)ak. For example, 3142 is well-balanced when n = 4. a) Prove that no permutation is well-balanced when n mod 4 = 2. b) Prove that if a1 . . . an is well-balanced, so are its reversal an . . . a1, its complement (n+1−a1) . . . (n+1−an), and its inverse a′ 1 . . . a′ n. c) Determine the number of well-balanced permutations for small values of n.
Verified: yes
Solve time: 4m06s
Let
$$ S(a_1\ldots a_n)=\sum_{k=1}^n k a_k. $$
The defining condition is
$$ \sum_{k=1}^n k a_k=\sum_{k=1}^n (n+1-k)a_k. $$
Expanding,
$$ \sum_{k=1}^n (n+1-k)a_k=(n+1)\sum_{k=1}^n a_k-\sum_{k=1}^n k a_k. $$
Since $a_1\ldots a_n$ is a permutation of ${1,\ldots,n}$,
$$ \sum_{k=1}^n a_k=\frac{n(n+1)}{2}. $$
Hence
$$ S(a)= (n+1)\frac{n(n+1)}{2}-S(a), $$
so
$$ 2S(a)=\frac{n(n+1)^2}{2},\qquad S(a)=\frac{n(n+1)^2}{4}. $$
Thus $a_1\ldots a_n$ is well-balanced if and only if
$$ \sum_{k=1}^n k a_k=\frac{n(n+1)^2}{4}. $$
a) Nonexistence for $n\equiv 2 \pmod 4$
Let $n=4m+2$. Then
$$ \frac{n(n+1)^2}{4}=\frac{(4m+2)(4m+3)^2}{4} =\frac{(2m+1)(4m+3)^2}{2}. $$
The factor $(2m+1)(4m+3)^2$ is odd, hence the expression is not an integer.
But $S(a)=\sum_{k=1}^n k a_k$ is always an integer. Therefore no permutation can satisfy the defining condition when $n\equiv 2\pmod 4$.
b) Symmetries
Let $a_1\ldots a_n$ be well-balanced and let
$$ T=\frac{n(n+1)^2}{4}. $$
Reversal
Define $b_k=a_{n+1-k}$. Then
$$ \sum_{k=1}^n k b_k=\sum_{k=1}^n k a_{n+1-k}. $$
Set $j=n+1-k$. Then
$$ \sum_{k=1}^n k a_{n+1-k}=\sum_{j=1}^n (n+1-j)a_j=T, $$
so the reversal is well-balanced.
Complement
Let $c_k=n+1-a_k$. Then
$$ \sum_{k=1}^n k c_k =(n+1)\sum_{k=1}^n k-\sum_{k=1}^n k a_k =(n+1)\frac{n(n+1)}{2}-T=T. $$
Inverse
Let $a'$ be the inverse permutation, so $a'_{a_k}=k$.
Consider the set of pairs ${(k,a_k)\mid 1\le k\le n}$. This is a bijection between positions and values. In these pairs, the identity $a'_{a_k}=k$ rewrites each pair as $(a_k,k)$.
Hence the multiset of ordered pairs is preserved under swapping coordinates, so
$$ \sum_{k=1}^n k a_k=\sum_{k=1}^n a_k a'_ {a_k}=\sum_{j=1}^n j a'_j. $$
Therefore $S(a)=S(a')$, and the inverse permutation is also well-balanced.
c) Enumeration for small $n$
We use the equivalent condition
$$ \sum_{k=1}^n k a_k=T_n=\frac{n(n+1)^2}{4}. $$
$n=1$
$$ 1\cdot 1 = (1+1-1)\cdot 1, $$
so there is $1$ solution.
$n=2$
Since $2\equiv 2\pmod 4$, part (a) implies no solutions:
$$ 0. $$
$n=3$
$$ T_3=\frac{3\cdot 16}{4}=12. $$
Direct evaluation:
$$ 123:14,\quad 132:13,\quad 213:13,\quad 231:11,\quad 312:11,\quad 321:10. $$
No permutation yields $12$, so the count is $0$.
$n=4$
$$ T_4=\frac{4\cdot 25}{4}=25. $$
We solve
$$ a_1+2a_2+3a_3+4a_4=25. $$
Case $a_4=4$
Remaining ${1,2,3}$, target:
$$ a_1+2a_2+3a_3=25-16=9. $$
Checking permutations of ${1,2,3}$, the possible values are $10,11,13,14$, so none equal $9$.
Case $a_4=3$
Remaining ${1,2,4}$, target:
$$ a_1+2a_2+3a_3=25-12=13. $$
Check permutations:
$$ (2,4,1):\ 2+8+3=13, $$
so
$$ a=(2,4,1,3)=2413. $$
No other permutation gives $13$.
Case $a_4=2$
Remaining ${1,3,4}$, target:
$$ a_1+2a_2+3a_3=25-8=17. $$
Check permutations:
$$ (3,1,4):\ 3+2+12=17, $$
so
$$ a=(3,1,4,2)=3142. $$
No other permutation gives $17$.
Case $a_4=1$
Remaining ${2,3,4}$, target:
$$ a_1+2a_2+3a_3=25-4=21. $$
But the maximum possible value is
$$ 1\cdot 2 + 2\cdot 3 + 3\cdot 4 = 20, $$
so this case is impossible.
Conclusion for $n=4$
Exactly two permutations satisfy the condition:
$$ 2413,\quad 3142. $$
Final answers for small $n$
$$ n=1:1,\quad n=2:0,\quad n=3:0,\quad n=4:2. $$
$$ \boxed{1,0,0,2}. $$