|
|
A089006
|
|
Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.
|
|
4
|
|
|
1, 2, 7, 45, 650, 24520, 2625117, 836488618, 818230288201, 2513135860300849, 24686082394548211147, 787959836124458000837941, 82905574521614049485027140026
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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.
|
|
REFERENCES
|
Adolf Mader and Otto Mutzbauer, "Double Orderings of (0,1) Matrices", Ars Combinatoria v. 61 (2001) pp 81-95.
|
|
LINKS
|
|
|
EXAMPLE
|
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}}.
|
|
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}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
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.
|
|
STATUS
|
approved
|
|
|
|