login
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.
3
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,1
COMMENTS
It is conjectured that for n>=3 the last term > 0 in row n is T(n,2*n-3). This is consistent with the result of random draws, where T(7,11) is the last term in row 7.
Approximate values ​​of the terms in the next row 7 from random drawings are as follows: 8.4E8, 3.79E12, 2.38E14, 2.54E14, 5.61E13, 1.02E13, 8.22E11, 9.0E10, 4.2E9, 3E8, 9E6, 1E6.
LINKS
Hugo Pfoertner, PARI program, computes row n.
Markus Sigg, C program, computes row n for A374525 or A374526.
FORMULA
For each n: Sum_{k>=0} T(n,k) = 2^(n^2).
T(n,0) = A089006(n).
EXAMPLE
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]
PROG
(PARI) \\ See link.
CROSSREFS
Cf. A002416 (row sums), A089006 (column 0), A374526.
Sequence in context: A251809 A016639 A138341 * A374526 A153520 A153649
KEYWORD
nonn,tabf,hard,more
AUTHOR
Hugo Pfoertner at the suggestion of Markus Sigg, Jul 19 2024
EXTENSIONS
a(24)-a(33) (row 6 of triangle) from Markus Sigg, Jul 25 2024
STATUS
approved