A374525 -id:A374525 - cp's OEIS frontend

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

Markus Sigg and Hugo Pfoertner, Jul 24 2024

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

			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

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

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)};

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

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

A089006 Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.

Original entry on oeis.org

1, 2, 7, 45, 650, 24520, 2625117, 836488618, 818230288201, 2513135860300849, 24686082394548211147, 787959836124458000837941, 82905574521614049485027140026

Offset: 0

Wouter Meeussen, Nov 03 2003

Also, number of n X n binary matrices with both rows and columns, considered as binary numbers, in nondecreasing order. (Ordering only rows gives A060690.) - R. H. Hardin, May 08 2008
A result of Adolf Mader and Otto Mutzbauer shows that the two definitions are equivalent. - Victor S. Miller, Feb 03 2009
For n=5, only 0.07% remain distinct. Sorting columns and\or rows does not change the permanent of the matrix and leaves the absolute value of the determinant unchanged.
Diagonal of A180985.

			The 7 (2 X 2)-matrices are {{0,0},{0,0}}, {{0,0},{0,1}}, {{0,0},{1,1}}, {{0,1},{0,1}}, {{0,1},{1,0}}, {{0,1},{1,1}} and {{1,1},{1,1}}.

Adolf Mader and Otto Mutzbauer, "Double Orderings of (0,1) Matrices", Ars Combinatoria v. 61 (2001) pp 81-95.

R. H. Hardin, Binary arrays with both rows and cols sorted, symmetries
M. Werner, An Algorithmic Approach for the Zarankiewicz Problem, Slides, 2012. - From _N. J. A. Sloane_, Jan 01 2013

Cf. A088672, A087981, A180985.

Column 0 of A374525.

baseform[li_List] := FixedPoint[Sort[Transpose[Sort[Transpose[Sort[ #1]]]]]&, li]; Table[Length@Split[Sort[baseform/@(Partition[ #, n]&/@(IntegerDigits[Range[0, -1+2^n^2], 2, n^2]))]], {n, 4}]

a(6)-a(12) found by R. H. Hardin, May 08 2008. These terms were found using bdd's (binary decision diagrams), just setting up the logical relations between bits in a gigantic bdd expression and using that to count the satisfying states.

Edited by N. J. A. Sloane, Feb 05 2009 at the suggestion of Victor S. Miller

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A089006 Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions