|
|
A232569
|
|
Triangle T(n, k) = number of non-equivalent (mod D_4) binary n X n matrices with k pairwise not adjacent 1's; k=0,...,n^2.
|
|
5
|
|
|
1, 1, 1, 1, 1, 0, 0, 1, 3, 6, 6, 3, 1, 0, 0, 0, 0, 1, 3, 17, 40, 62, 45, 20, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 43, 210, 683, 1425, 1936, 1696, 977, 366, 101, 21, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 84, 681, 4015, 16149, 46472, 95838, 143657
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,9
|
|
COMMENTS
|
Also number of non-equivalent ways to place k non-attacking wazirs on an n X n board.
Two matrix elements are considered adjacent, if the difference of their row indices is 1 and the column indices are equal, or vice versa (von Neumann neighborhood).
Counted for this sequence are equivalence classes induced by the dihedral group D_4. If equivalent matrices are being destinguished, the corresponding numbers are A232833(n).
Row index starts from n = 1, column index k ranges from 0 to n^2.
Into an n X n binary matrix there can be placed maximally A000982(n) = ceiling(n^2/2) pairwise not adjacent 1's.
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
1,1;
1,1,1,0,0;
1,3,6,6,3,1,0,0,0,0;
1,3,17,40,62,45,20,4,1,0,0,0,0,0,0,0,0;
1,6,43,210,683,1425,1936,1696,977,366,101,21,5,1,0,0,0,0,0,0,0,0,0,0,0,0;
...
There are T(3, 2) = 6 non-equivalent binary 3 X 3 matrices with 2 not adjacent 1's (and no other 1's):
[1 0 0] [0 1 0] [1 0 0] [0 1 0] [1 0 1] [1 0 0]
|0 0 0| |0 0 0| |0 1 0| |1 0 0| |0 0 0| |0 0 1|
[0 0 1] [0 1 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|