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

Author

Hugo Pfoertner at the suggestion of Markus Sigg, Jul 19 2024

Keywords

• nonn
• tabf
• hard
• more

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.

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.

Crossrefs

Cf. A002416 (row sums), A089006 (column 0), 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