|
| |
|
|
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.
|
|
6
|
|
|
|
0, 1, 1, 2, 5, 13, 42, 155, 636, 2889, 14321, 76834, 443157
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Better definition and values of a(12)-a(13) from R. H. Hardin, Sep 17 2013
|
|
|
STATUS
|
approved
|
| |
|
|
