A374526 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

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

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

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

Adjacent sequences: A374523 A374524 A374525 * A374527 A374528 A374529

KEYWORD

nonn,tabf,hard,more

AUTHOR

Markus Sigg and Hugo Pfoertner, Jul 24 2024

STATUS

approved