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

%I #40 Mar 03 2022 10:11:41

%S 1,3,7,14,25,41,64,95,136,189,256,339,441,564,711,885,1089,1326,1600,

%T 1914,2272,2678,3136,3650,4225,4865,5575,6360,7225,8175,9216,10353,

%U 11592,12939,14400,15981,17689,19530,21511,23639,25921,28364,30976

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

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

%H Author?, <a href="/A057524/b057524.txt">Table of n, a(n) for n = 0..1374</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,0,1,2,-3,1).

%F (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.

%F G.f.: 1/(1-x^3)/(1-x^2)/(1-x)^3.

%F 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

%F a(n) = Sum_{m=0..n} (n-m+1)*floor(((m+3)^2+3)/12). [_Renzo Benedetti_, Sep 30 2009]

%F a(n) = floor( ((n+2)*(n+6)/12)^2 ) = round( ((n+2)*(n+6)/12)^2 ). [_Renzo Benedetti_, Jul 25 2012]

%F Partial sums of A000601. - _R. J. Mathar_, Jul 25 2012

%e There are 7 binary 3x2 matrices without unit columns up to row and column permutations:

%e [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]

%e [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]

%e [0 0] [0 1] [1 1] [0 1] [1 1] [1 1] [1 1].

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

%Y Cf. A038846 for labeled case.

%Y Cf. A000217, A002623, A002620.

%K nonn,easy

%O 0,2

%A _Vladeta Jovovic_, Sep 02 2000

%E More terms from _James A. Sellers_, Sep 07 2000