A229161 Number of n X n binary matrices with exactly 2 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

0, 1, 1, 2, 5, 13, 42, 155, 636, 2889, 14321, 76834, 443157

Offset: 1

Author

N. J. A. Sloane, Sep 15 2013

Keywords

• nonn
• more

Comments

A column of A227061.

From Brendan McKay, Sep 16 2013: (Start)

If all row and column permutations are allowed, one gets A002865 for k=2, A000512 for k=3, A000513 for k=4, A000516 for k=5, etc., where k = number of 1's in each row and column. See also A133687.

A229161 is strictly different from A002865, which gives the number of equivalence classes of n X n binary matrices with exactly 2 1's in each row and column, up to permutations of rows and columns.

For example, take two non-equivalent n X n matrices A,B which are in sorted form (i.e. the rows are in increasing order and so are the columns). Now form a 2n X 2n matrix by placing A and B in the off-diagonal blocks and zeros in the two diagonal blocks. This matrix is in sorted form. Interchanging A and B gives a different matrix that is also in sorted form, and yet it is easily produced from the first matrix by permuting rows and columns. That is, one equivalence class can contain two different sorted matrices. I expect that on average the number of sorted matrices per equivalence class is exponentially large.

(End)

References

• K. Yordzhev, On an Algorithm for Isomorphism-Free Generations of Combinatorial Objects, International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Web Site: www.ijettcs.org, Volume 2, Issue 6, November - December 2013, ISSN 2278-6856

Links

• K. Yordzhev, Fibonacci sequence related to a combinatorial problem on binary matrices, arXiv preprint arXiv:1305.6790, 2013
• K. Yordzhev, Semi-canonical binary matrices, arXiv preprint arXiv:1506.04642, 2015

Crossrefs

Cf. A229162, A229163, A229164, A181344, A181345, A002865, A000512, A000513, A000516, A133687.

Extensions

Better definition and values of a(12)-a(13) from R. H. Hardin, Sep 17 2013