A374526 Similar to A374525, but for each starting matrix with a choice of whether to sort by columns or rows first, such that the total number of sorting steps for this matrix is minimized.

2, 7, 7, 2, 45, 254, 212, 1, 650, 19500, 44463, 899, 20, 4, 24520, 4347402, 27123390, 1978573, 72427, 7940, 144, 36, 2625117, 3107244605, 53818094633, 11242079280, 512469215, 35810192, 1002242, 148572, 2304, 576, 836488618

Offset: 1

Author

Markus Sigg and Hugo Pfoertner, Jul 24 2024

Keywords

• nonn
• tabf
• hard
• more

Comments

This irregular triangle, read by rows, has the same structure as that of A374525, but differs starting from row 3.

Examples

			The triangle begins
   \ k    0        1         2        3      4     5    6   7
  n  --------------------------------------------------------
  1 |     2,
  2 |     7,       7,        2,
  3 |    45,     254,      212,       1,
  4 |   650,   19500,    44463,     899,    20,    4,
  5 | 24520, 4347402, 27123390, 1978573, 72427, 7940, 144, 36
.
T(3,3) = 1 because only one ([1,1,0; 1,0,1; 0,1,0]) of the A374525(3,3) = 5 matrices needs 3 sort steps irrespective of the initial sorting direction, whereas the other 4 ([0,1,1; 1,1,0; 0,0,1], [1,0,1; 0,1,1; 1,0,0], [1,0,1; 1,1,0; 0,0,1], [1,1,0; 0,1,1; 1,0,0]) can be sorted in a single step by choosing the "better" direction.
.
                  Sorting by
       Rows     Cols     Rows     Cols stable
  1 1 0    0 1 0    0 0 1    0 0 1    0 0 1
  1 0 1    1 0 1    1 1 0    0 1 1    0 1 1
  0 1 0    1 1 0    0 1 1    1 1 0    1 1 0     3 sort steps needed
                                                for both choices
       Cols     Rows     Cols     Rows stable   of initial sorting
  1 1 0    0 1 1    0 1 0    0 0 1    0 0 1     direction
  1 0 1    1 0 1    0 1 1    0 1 1    0 1 1
  0 1 0    0 1 0    1 0 1    1 1 0    1 1 0
.
       Rows     Cols stable        Cols     Rows     Cols     Rows stable
  0 1 1    0 0 1    0 0 1  |  0 1 1    0 1 1    0 1 0    0 0 1    0 0 1
  1 1 0    0 1 1    0 1 1  |  1 1 0    1 0 1    0 1 1    0 1 1    0 1 1
  0 0 1    1 1 0    1 1 0  |  0 0 1    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 0 1    0 1 1    0 1 1  |  1 0 1    0 1 1    0 1 0    0 0 1    0 0 1
  0 1 1    1 0 0    1 0 0  |  0 1 1    1 0 1    0 1 1    0 1 1    0 1 1
  1 0 0    1 0 1    1 0 1  |  1 0 0    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 0 1    0 0 1    0 0 1  |  1 0 1    0 1 1    0 1 0    0 0 1    0 0 1
  1 1 0    1 0 1    1 0 1  |  1 1 0    1 0 1    0 1 1    0 1 1    0 1 1
  0 0 1    1 1 1    1 1 1  |  0 0 1    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 1 0    0 1 1    0 1 1  |  1 1 0    0 1 1    0 1 0    0 0 1    0 0 1
  0 1 1    1 0 0    1 0 0  |  0 1 1    1 0 1    0 1 1    0 1 1    0 1 1
  1 0 0    1 1 0    1 0 1  |  1 0 0    0 1 0    1 0 1    1 1 0    1 1 0
    1 sort step needed               3 sort steps needed
.
T(4,5)=4, because there are 4 matrices needing 5 sort steps irrespective of the choice of the initial sorting direction.
[1,1,0,1; 1,0,1,1; 0,1,1,0; 1,1,0,0], [1,1,1,0; 1,0,1,1; 0,1,0,1; 1,1,0,0],
[1,1,0,1; 1,0,1,1; 1,1,0,0; 0,1,1,0], [1,1,1,0; 1,0,1,1; 1,1,0,0; 0,1,0,1].
Routes of sorting for the first of these matrices, both with 5 steps:
         Cols       Rows       Cols       Rows       Cols       Rows stable
  1 1 0 1    0 1 1 1    0 1 0 1    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  1 0 1 1    1 0 1 1    0 1 1 1    0 1 1 1    0 1 1 1    0 1 1 1    0 1 1 1
  0 1 1 0    1 1 0 0    1 0 1 1    1 1 0 1    1 0 1 0    1 0 0 1    1 0 0 1
  1 1 0 0    0 1 0 1    1 1 0 0    1 0 1 0    1 1 0 1    1 1 1 0    1 1 1 0
or
         Rows       Cols       Rows       Cols       Rows       Cols stable
  1 1 0 1    0 1 1 0    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  1 0 1 1    1 0 1 1    1 1 0 1    0 1 1 0    0 1 0 1    0 1 0 1    0 1 0 1
  0 1 1 0    1 1 0 0    0 1 1 0    1 1 0 1    1 1 1 0    1 1 0 1    1 1 0 1
  1 1 0 0    1 1 0 1    1 1 1 0    1 1 1 0    1 1 0 1    1 1 1 0    1 1 1 0
		

Crossrefs

Cf. A002416 (row sums), A089006 (column 0), A374525.

Programs

PARI

numberOfSortSteps(M, f) = {my(c=0, M1 = if (f == 0, vecsort(M), vecsort(M~)~)); if (M != M1, M = M1; c++); while (1, f = !f; M1 = if (f == 0, vecsort(M), vecsort(M~)~); if (M != M1, M = M1; c++, return(c)))};
minNumberOfSortSteps(M) = min(numberOfSortSteps(M, 0), numberOfSortSteps(M, 1));
a374526(n) = {my(v = vector(n*n), M = matrix(n,n)); while (1, v[minNumberOfSortSteps(M) + 1]++; for (i = 1, n, for (j = 1, n, if (M[i,j]++ == 1, break(2), M[i,j]=0); if (i == n && j == n, break(3))))); select(x->x>0, v)};

Formula

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

Sum_{k>=0} T(n,k) = 2^(n^2).