A374525 - OEIS

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.

%I #39 Jul 30 2024 04:16:51

%S 2,7,7,2,45,219,243,5,650,13599,46385,4512,344,46,24520,2542012,

%T 23807149,6258387,781647,132869,7134,714,2625117,1649029775,

%U 39954292931,22532640821,3839779352,685879134,49418375,5578311,215664,17256,836488618

%N 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.

%C 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.

%C 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.

%H Hugo Pfoertner, <a href="/A374525/a374525.gp.txt">PARI program</a>, computes row n.

%H Markus Sigg, <a href="/A374525/a374525.c.txt">C program</a>, computes row n for A374525 or A374526.

%F For each n: Sum_{k>=0} T(n,k) = 2^(n^2).

%F T(n,0) = A089006(n).

%e The triangle begins

%e \ k 0 1 2 3 4 5 6 7

%e n -------------------------------------------------------------

%e 1 | 2,

%e 2 | 7, 7, 2,

%e 3 | 45, 219, 243, 5,

%e 4 | 650, 13599, 46385, 4512, 344, 46,

%e 5 | 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714

%e .

%e T(2,0) = 7;

%e matrices that are already stably sorted, i.e., neither affected

%e by sorting by rows nor by sorting by columns:

%e [0, 0; 0, 0], [0, 0; 0, 1], [0, 0; 1, 1], [0, 1; 0, 1],

%e [0, 1; 1, 0], [0, 1; 1, 1], [1, 1; 1, 1]

%e .

%e T(2,1) = 7; matrices that become stable after one sort:

%e sorting by stable

%e [0, 0; 1, 0] columns -> [0, 0; 0, 1]

%e [0, 1; 0, 0] rows -> [0, 0; 0, 1]

%e [1, 0; 0, 1] rows or -> [0, 1; 1, 0]

%e columns

%e [1, 0; 1, 0] columns -> [0, 1; 0, 1]

%e [1, 0; 1, 1] columns -> [0, 1; 1, 1]

%e [1, 1; 0, 0] rows -> [0, 0; 1, 1]

%e [1, 1; 0, 1] rows -> [0, 1; 1, 1]

%e .

%e T(2,2) = 2; matrices needing two sorts to become stable:

%e sorting by stable

%e [1, 0] [0, 1] [0, 0]

%e [0, 0] [0, 0] [0, 1]

%e columns -> rows ->

%e [1, 1] [1, 1] [0, 1]

%e [1, 0] [0, 1] [1, 1]

%o (PARI) \\ See link.

%Y Cf. A002416 (row sums), A089006 (column 0), A374526.

%K nonn,tabf,hard,more

%O 1,1

%A _Hugo Pfoertner_ at the suggestion of _Markus Sigg_, Jul 19 2024

%E a(24)-a(33) (row 6 of triangle) from _Markus Sigg_, Jul 25 2024