login
Number of 3 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (10;1).
0

%I #17 Dec 22 2018 16:24:12

%S 1,8,24,58,128,270,556,1130,2280,4582,9188,18402,36832,73694,147420,

%T 294874,589784,1179606,2359252,4718546,9437136,18874318,37748684,

%U 75497418,150994888,301989830,603979716,1207959490,2415919040,4831838142,9663676348,19327352762

%N Number of 3 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (10;1).

%C An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1<i2, j1<j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by g.f. 2xy/((1-2x)(1-(2-x)y/(1-x))).

%H S. Kitaev, <a href="http://www.emis.de/journals/INTEGERS/papers/e21/e21.Abstract.html">On multi-avoidance of right angled numbered polyomino patterns</a>, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.

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

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

%F a(n) = 9*2^n - 2*n - 8.

%F a(n) = 2 * (A054127(n+1) - 1) for n>0.

%o (PARI) vector(50, n, 9*2^n - 2*n - 8) \\ _Michel Marcus_, Dec 01 2014

%Y Cf. A054127.

%K nonn,easy

%O 0,2

%A _Sergey Kitaev_, Nov 13 2004

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 21 2018