login
Number of 3 X n binary matrices with no zero rows or columns.
3

%I #22 Mar 18 2024 16:47:08

%S 1,25,265,2161,16081,115465,816985,5745121,40294561,282298105,

%T 1976795305,13839692881,96884227441,678208723945,4747518463225,

%U 33232801429441,232630126566721,1628412435648985,11398891698588745,79792255837258801,558545832702224401

%N Number of 3 X n binary matrices with no zero rows or columns.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (11,-31,21).

%F Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.

%F a(n) = 7^n-3*3^n+3.

%F a(n) = 11*a(n-1)-31*a(n-2)+21*a(n-3). G.f.: -x*(21*x^2+14*x+1) / ((x-1)*(3*x-1)*(7*x-1)). - _Colin Barker_, Jul 10 2013

%t LinearRecurrence[{11,-31,21},{1,25,265},30] (* _Harvey P. Dale_, Aug 15 2014 *)

%o (PARI) a(n) = 7^n-3*3^n+3 \\ _Charles R Greathouse IV_, Feb 10 2017

%Y Cf. A055602, A024206, A055609 (unlabeled case), A058481, column 3 of A183109 and A218695.

%K easy,nonn,nice

%O 1,2

%A _Vladeta Jovovic_, Nov 26 2000

%E More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

%E More terms from _Colin Barker_, Jul 10 2013