|
|
A057524
|
|
Number of 3 x n binary matrices without unit columns up to row and column permutations.
|
|
16
|
|
|
1, 3, 7, 14, 25, 41, 64, 95, 136, 189, 256, 339, 441, 564, 711, 885, 1089, 1326, 1600, 1914, 2272, 2678, 3136, 3650, 4225, 4865, 5575, 6360, 7225, 8175, 9216, 10353, 11592, 12939, 14400, 15981, 17689, 19530, 21511, 23639, 25921, 28364, 30976
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Unit column of a binary matrix is a column with only one 1. First differences of a(n) give number of minimal 3-covers of an unlabeled n-set that cover 3 points of that set uniquely (if offset is 3).
|
|
LINKS
|
|
|
FORMULA
|
(1/6)*(Z(S_n; 5, 5, ...)+3*Z(S_n; 3, 5, 3, 5, ...)+2*Z(S_n; 2, 2, 5, 2, 2, 5, ...)) where Z(S_n; x_1, x_2, x_3, ...) is cycle index of symmetric group S_n of degree n.
G.f.: 1/(1-x^3)/(1-x^2)/(1-x)^3.
Let P(i,k) be the number of integer partitions of n into k parts, then with k=3 we have a(n) = Sum_{m=1..n} Sum_{i=k..m} P(i,k). - Thomas Wieder, Feb 18 2007
a(n) = Sum_{m=0..n} (n-m+1)*floor(((m+3)^2+3)/12). [Renzo Benedetti, Sep 30 2009]
a(n) = floor( ((n+2)*(n+6)/12)^2 ) = round( ((n+2)*(n+6)/12)^2 ). [Renzo Benedetti, Jul 25 2012]
|
|
EXAMPLE
|
There are 7 binary 3x2 matrices without unit columns up to row and column permutations:
[0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
[0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]
[0 0] [0 1] [1 1] [0 1] [1 1] [1 1] [1 1].
|
|
MATHEMATICA
|
CoefficientList[ Series[ 1/(1 - x^3)/(1 - x^2)/(1 - x)^3, {x, 0, 42}], x] (* Jean-François Alcover, Mar 26 2013 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|