login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

Diagonal of A180985.

REFERENCES

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

M. Werner, An Algorithmic Approach for the Zarankiewicz Problem, http://tubafun.bplaced.net/public/zarankiewicz_paper_presentation.pdf, 2012. - From N. J. A. Sloane, Jan 01 2013

LINKS

Table of n, a(n) for n=0..12.

R. H. Hardin, Binary arrays with both rows and cols sorted, symmetries

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

Cf. A088672, A087981, A180985.

Sequence in context: A162049 A162050 A162051 * A019004 A027328 A111842

Adjacent sequences:  A089003 A089004 A089005 * A089007 A089008 A089009

KEYWORD

nonn

AUTHOR

Wouter Meeussen, Nov 03 2003

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 25 16:08 EDT 2017. Contains 287039 sequences.