|
%I #29 Nov 13 2023 04:45:25
%S 1,2,7,45,650,24520,2625117,836488618,818230288201,2513135860300849,
%T 24686082394548211147,787959836124458000837941,
%U 82905574521614049485027140026
%N Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.
%C 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
%C A result of Adolf Mader and Otto Mutzbauer shows that the two definitions are equivalent. - _Victor S. Miller_, Feb 03 2009
%C 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.
%C Diagonal of A180985.
%D Adolf Mader and Otto Mutzbauer, "Double Orderings of (0,1) Matrices", Ars Combinatoria v. 61 (2001) pp 81-95.
%H R. H. Hardin, <a href="/A151801/a151801.txt">Binary arrays with both rows and cols sorted, symmetries</a>
%H M. Werner, <a href="https://web.archive.org/web/20171109081752/http://tubafun.bplaced.net/public/zarankiewicz_paper_presentation.pdf">An Algorithmic Approach for the Zarankiewicz Problem</a>, Slides, 2012. - From _N. J. A. Sloane_, Jan 01 2013
%e 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}}.
%t 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}]
%Y Cf. A088672, A087981, A180985.
%K nonn,more
%O 0,2
%A _Wouter Meeussen_, Nov 03 2003
%E 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.
%E Edited by _N. J. A. Sloane_, Feb 05 2009 at the suggestion of _Victor S. Miller_
|
