OFFSET
0,3
COMMENTS
For a permutation sigma of {1,...,n}, place the positions 1,...,n from left to right on a line.
For each position i, shade sigma(i) consecutive positions starting at i. If i is odd, the shading moves to the left; if i is even, it moves to the right. Whenever the motion reaches an endpoint, it is reflected, with the endpoint counted again after the reflection.
The statistic E(sigma) measures the non-uniformity of the shading produced by the permutation. The value m is the maximum number of complete uniform layers that can be removed from all positions simultaneously. Therefore E(sigma) is exactly the amount of shading that remains after all common uniform coverage has been removed.
In particular, E(sigma)=0 if and only if all positions are shaded equally often. Larger values of E(sigma) correspond to greater imbalance in the coverage of the positions.
The sequence sums E(sigma) over all permutations in S_n in order to measure the aggregate non-uniformity of this reflected shading process at size n. Thus a(n) is not associated with one particular permutation, but records the total excess shading generated by the entire permutation class S_n. This provides a global permutation statistic obtained from the reflected interval-shading rule.
FORMULA
a(n) = n!*n*(n+1)/2 - n*Sum_{sigma in S_n} m_sigma, where m_sigma = min (c_sigma(1),...,c_sigma(n)) and c_sigma(j) is the number of times position j is shaded.
EXAMPLE
For example, for n=5 and i=4 with sigma(4)=5, the visited positions are
4 -> 5 -> 5 -> 4 -> 3.
For n=4 and i=3 with sigma(3)=4, the visited positions are 3 -> 2 -> 1 -> 1.
For n=5 and sigma=(3,2,5,1,4), the complete reflected shading process is:
i=1, sigma(1)=3: 1 1 2
i=2, sigma(2)=2: 2 3
i=3, sigma(3)=5: 3 2 1 1 2
i=4, sigma(4)=1: 4
i=5, sigma(5)=4: 5 4 3 2
The total shading counts are: c(1),c(2),c(3),c(4),c(5) = 4,5,3,2,1.
The minimum is m = min(c(1),...,c(5)) = 1.
After removing one complete uniform layer, the excess counts are
(c(1)-m, c(2)-m, c(3)-m, c(4)-m, c(5)-m) = (3,4,2,1,0)
Therefore: E(sigma) = 3+4+2+1+0 = 10.
For n=3 the six permutations are 123, 132, 213, 231, 312, 321. Their excess shadings are respectively 0, 2, 2, 4, 2, 2. Therefore a(3)=0+2+2+4+2+2=12.
For n=4 take the permutation sigma = (2,1,4,3).
The positions are: 1 2 3 4
For i=1 (odd), sigma(1)=2, shade left: 1 1
For i=2 (even), sigma(2)=1, shade right: 2
For i=3 (odd), sigma(3)=4, shade left with reflection: 3 2 1 1
For i=4 (even), sigma(4)=3, shade right with reflection: 4 4 3
The total shading counts are c = (4,2,2,2). The minimum shading is m = 2.
Therefore the excess shadings of positions are (2,0,0,0) and the excess shadings of the permutation is E(sigma)=2.
PROG
(Python)
from itertools import permutations
from math import factorial
def m(p):
n=len(p); c=[0]*n
for i, k in enumerate(p, 1):
d=-1 if i%2 else 1; x=i
for _ in range(k):
c[x-1]+=1
y=x+d
if y<1 or y>n: d=-d; y=x
x=y
return min(c)
def a(n):
if n==0: return 0
return factorial(n)*n*(n+1)//2-n*sum(m(p) for p in permutations(range(1, n+1)))
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Marko Radulovic, Jul 20 2026
EXTENSIONS
a(11)-a(14) from Sean A. Irvine, Aug 14 2026
STATUS
approved