A374525 T(n,k) is the number of distinct n X n {0,1}-matrices that reach a fixed point after k alternately applied sorts by rows and columns, where T(n,k), k>=0 is an irregular triangle read by rows.
2, 7, 7, 2, 45, 219, 243, 5, 650, 13599, 46385, 4512, 344, 46, 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714, 2625117, 1649029775, 39954292931, 22532640821, 3839779352, 685879134, 49418375, 5578311, 215664, 17256, 836488618
Offset: 1
Examples
The triangle begins
\ k 0 1 2 3 4 5 6 7
n -------------------------------------------------------------
1 | 2,
2 | 7, 7, 2,
3 | 45, 219, 243, 5,
4 | 650, 13599, 46385, 4512, 344, 46,
5 | 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714
.
T(2,0) = 7;
matrices that are already stably sorted, i.e., neither affected
by sorting by rows nor by sorting by columns:
[0, 0; 0, 0], [0, 0; 0, 1], [0, 0; 1, 1], [0, 1; 0, 1],
[0, 1; 1, 0], [0, 1; 1, 1], [1, 1; 1, 1]
.
T(2,1) = 7; matrices that become stable after one sort:
sorting by stable
[0, 0; 1, 0] columns -> [0, 0; 0, 1]
[0, 1; 0, 0] rows -> [0, 0; 0, 1]
[1, 0; 0, 1] rows or -> [0, 1; 1, 0]
columns
[1, 0; 1, 0] columns -> [0, 1; 0, 1]
[1, 0; 1, 1] columns -> [0, 1; 1, 1]
[1, 1; 0, 0] rows -> [0, 0; 1, 1]
[1, 1; 0, 1] rows -> [0, 1; 1, 1]
.
T(2,2) = 2; matrices needing two sorts to become stable:
sorting by stable
[1, 0] [0, 1] [0, 0]
[0, 0] [0, 0] [0, 1]
columns -> rows ->
[1, 1] [1, 1] [0, 1]
[1, 0] [0, 1] [1, 1]
Links
- Hugo Pfoertner, PARI program, computes row n.
- Markus Sigg, C program, computes row n for A374525 or A374526.
Programs
-
PARI
\\ See link.
Formula
For each n: Sum_{k>=0} T(n,k) = 2^(n^2).
T(n,0) = A089006(n).
Extensions
a(24)-a(33) (row 6 of triangle) from Markus Sigg, Jul 25 2024
Comments