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

%I #28 Feb 13 2022 05:00:57

%S 1,16,46,106,226,466,946,1906,3826,7666,15346,30706,61426,122866,

%T 245746,491506,983026,1966066,3932146,7864306,15728626,31457266,

%U 62914546,125829106,251658226,503316466,1006632946,2013265906,4026531826

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

%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 2^(m+n) - 2^m - 2^n + 2.

%C Binomial transform of 1,15,15,... (15 infinitely repeated). - _Gary W. Adamson_, Apr 29 2008

%C The binomial transform of [1, c, c, c, ...] has the terms a(n) = 1 - c + c*2^(n-1) if the offset 1 is chosen. The o.g.f. of the a(n) is x*(1+(c-2)x)/((2x-1)*(x-1)). This applies to A139634 with c=10, to A139635 with c=11, to A139697 with c=12, to A139698 with c=25 and to A099003, A139700, A139701 accordingly. - _R. J. Mathar_, May 11 2008

%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_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).

%F a(n) = 15*2^n - 14.

%F O.g.f.: (1+13x)/((x-1)(2x-1)). - _R. J. Mathar_, May 06 2008

%t LinearRecurrence[{3,-2},{1,16},40] (* _Harvey P. Dale_, May 20 2018 *)

%Y Cf. A048489 (m=3).

%K nonn,easy

%O 0,2

%A _Sergey Kitaev_, Nov 13 2004