A376790 Table T(n,k) read by antidiagonals: T(n,k) (n >=1, k >= 2) is the number of inversions in the radix-k digit reversal permutation of 0, 1, ..., k^n-1.

0, 0, 1, 0, 9, 8, 0, 36, 135, 44, 0, 100, 864, 1458, 208, 0, 225, 3500, 15552, 14094, 912, 0, 441, 10800, 95000, 258048, 130491, 3840, 0, 784, 27783, 413100, 2425000, 4174848, 1187541, 15808

Offset: 1

Author

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Oct 04 2024

Keywords

• nonn
• tabl

Comments

T(n,k) is also the maximum possible number of inversions in the sequence of chips in the (n+1)-st layer of the tree in the stable configuration resulting from directed chip-firing of k^n labeled chips 1, 2, ..., k^n starting at the root of an infinite, rooted directed k-ary tree. See Theorem 6.1 in Inagaki, Khovanova, and Luo (2024).

Examples

			For n=3, k=2, the radix-2 digit reversal permutation of 0, 1, 2, ..., 2^3-1 is 0, 4, 2, 6, 1, 5, 3, 7. This permutation has 8 inversions.
Array begins:
=======================================================
n/k |    2        3          4           5            6
----+--------------------------------------------------
  1 |    0        0          0           0            0 ...
  2 |    1        9         36         100          225 ...
  3 |    8      135        864        3500        10800 ...
  4 |   44     1458      15552       95000       413100 ...
  5 |  208    14094     258048     2425000     15066000 ...
  6 |  912   130491    4174848    60937500    543834000 ...
  7 | 3840  1187541   67018752  1525312500  19588521600 ...
  ...
		

Links

• David M. W. Evans, An Improved Digit-Reversal Permutation Algorithm for the Fast Fourier and Hartley Transforms, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-35, No. 8 (1987), 1120-1125.
• Ryota Inagaki, Tanya Khovanova, and Austin Luo, Chip Firing on Directed k-ary Trees, arXiv:2410.23265 [math.CO], 2024.
• Wikipedia, Bit-reversal Permutation

Crossrefs

Cf. A100575 (column 2).

Programs

Python

s = ""
for d in range(3, 11):
    for n in range(1, d-1):
        k = d-n
        s = s + str((k**(2*n) -  (n* (k**(n+1))) + (n-1) * (k**n))//4) + ", "
print(s)

Formula

T(n, k) = (k^(2*n) - n*k^(n+1) + (n-1)*k^n) / 4.