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,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

Table of n, a(n) for n=1..33.

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

Adjacent sequences: A374522 A374523 A374524 * A374526 A374527 A374528

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