A057524 Number of 3 x n binary matrices without unit columns up to row and column permutations.

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

Offset: 0

Author

Vladeta Jovovic, Sep 02 2000

Keywords

• nonn
• easy

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).

Examples

			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].
		

Links

• Author?, Table of n, a(n) for n = 0..1374
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,0,1,2,-3,1).

Crossrefs

Cf. A038846 for labeled case.

Cf. A000217, A002623, A002620.

Programs

Mathematica

CoefficientList[ Series[ 1/(1 - x^3)/(1 - x^2)/(1 - x)^3, {x, 0, 42}], x] (* Jean-François Alcover, Mar 26 2013 *)

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]

Partial sums of A000601. - R. J. Mathar, Jul 25 2012

Extensions

More terms from James Sellers, Sep 07 2000