login
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
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,1
COMMENTS
This irregular triangle, read by rows, has the same structure as that of A374525, but differs starting from row 3.
FORMULA
T(n,0) = A089006(n).
Sum_{k>=0} T(n,k) = 2^(n^2).
EXAMPLE
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
PROG
(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)};
CROSSREFS
Cf. A002416 (row sums), A089006 (column 0), A374525.
Sequence in context: A016639 A138341 A374525 * A153520 A153649 A020770
KEYWORD
nonn,tabf,hard,more
AUTHOR
Markus Sigg and Hugo Pfoertner, Jul 24 2024
STATUS
approved