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
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.
Comments