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

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

Offset: 0

Author

Wouter Meeussen, Nov 03 2003

Keywords

• nonn
• hard
• more

Comments

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.

Examples

			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}}.
		

References

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

Links

• 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

Crossrefs

Cf. A088672, A087981, A180985.

Column 0 of A374525.

Programs

Mathematica

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}]

Extensions

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