cp's OEIS Frontend

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 A374525 #43 Apr 25 2025 23:39:25
%S A374525 2,7,7,2,45,219,243,5,650,13599,46385,4512,344,46,24520,2542012,
%T A374525 23807149,6258387,781647,132869,7134,714,2625117,1649029775,
%U A374525 39954292931,22532640821,3839779352,685879134,49418375,5578311,215664,17256,836488618
%N 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.
%C A374525 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 A374525 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 A374525 Hugo Pfoertner, <a href="/A374525/a374525.gp.txt">PARI program</a>, computes row n.
%H A374525 Markus Sigg, <a href="/A374525/a374525.c.txt">C program</a>, computes row n for A374525 or A374526.
%F A374525 For each n: Sum_{k>=0} T(n,k) = 2^(n^2).
%F A374525 T(n,0) = A089006(n).
%e A374525 The triangle begins
%e A374525    \ k    0        1         2        3       4       5     6    7
%e A374525   n  -------------------------------------------------------------
%e A374525   1 |     2,
%e A374525   2 |     7,       7,        2,
%e A374525   3 |    45,     219,      243,       5,
%e A374525   4 |   650,   13599,    46385,    4512,    344,     46,
%e A374525   5 | 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714
%e A374525 .
%e A374525   T(2,0) = 7;
%e A374525   matrices that are already stably sorted, i.e., neither affected
%e A374525   by sorting by rows nor by sorting by columns:
%e A374525   [0, 0; 0, 0], [0, 0; 0, 1], [0, 0; 1, 1], [0, 1; 0, 1],
%e A374525   [0, 1; 1, 0], [0, 1; 1, 1], [1, 1; 1, 1]
%e A374525 .
%e A374525   T(2,1) = 7; matrices that become stable after one sort:
%e A374525                sorting by     stable
%e A374525   [0, 0; 1, 0] columns ->  [0, 0; 0, 1]
%e A374525   [0, 1; 0, 0] rows    ->  [0, 0; 0, 1]
%e A374525   [1, 0; 0, 1] rows or ->  [0, 1; 1, 0]
%e A374525                columns
%e A374525   [1, 0; 1, 0] columns ->  [0, 1; 0, 1]
%e A374525   [1, 0; 1, 1] columns ->  [0, 1; 1, 1]
%e A374525   [1, 1; 0, 0] rows    ->  [0, 0; 1, 1]
%e A374525   [1, 1; 0, 1] rows    ->  [0, 1; 1, 1]
%e A374525 .
%e A374525   T(2,2) = 2; matrices needing two sorts to become stable:
%e A374525          sorting            by     stable
%e A374525   [1, 0]            [0, 1]         [0, 0]
%e A374525   [0, 0]            [0, 0]         [0, 1]
%e A374525          columns ->        rows ->
%e A374525   [1, 1]            [1, 1]         [0, 1]
%e A374525   [1, 0]            [0, 1]         [1, 1]
%o A374525 (PARI) \\ See link.
%Y A374525 Cf. A002416 (row sums), A089006 (column 0), A374526.
%K A374525 nonn,tabf,hard,more
%O A374525 1,1
%A A374525 _Hugo Pfoertner_ at the suggestion of _Markus Sigg_, Jul 19 2024
%E A374525 a(24)-a(33) (row 6 of triangle) from _Markus Sigg_, Jul 25 2024