login
A100314
Number of 2 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (01;0), (10;0) and (01;1).
11
1, 4, 8, 14, 24, 42, 76, 142, 272, 530, 1044, 2070, 4120, 8218, 16412, 32798, 65568, 131106, 262180, 524326, 1048616, 2097194, 4194348, 8388654, 16777264, 33554482, 67108916, 134217782, 268435512, 536870970, 1073741884, 2147483710, 4294967360, 8589934658
OFFSET
0,2
COMMENTS
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 + 2^n + 2*(n*m-n-m).
REFERENCES
Arthur H. Stroud, Approximate calculation of multiple integrals, Prentice-Hall, 1971.
LINKS
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
FORMULA
a(n) = 2^n + 2*n.
From Gary W. Adamson, Jul 20 2007: (Start)
Binomial transform of (1, 3, 1, 1, 1, ...).
For n > 0, a(n) = 2*A005126(n-1). (End)
From R. J. Mathar, Jun 13 2008: (Start)
G.f.: 1 + 2*x*(2 -4*x +x^2)/((1-x)^2*(1-2*x)).
a(n+1)-a(n) = A052548(n). (End)
From Colin Barker, Oct 16 2013: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).
G.f.: (1 - 3*x^2)/((1-x)^2*(1-2*x)). (End)
E.g.f.: exp(2*x) + 2*x*exp(x). - Franck Maminirina Ramaharo, Dec 19 2018
a(n) = A000079(n) + A005843(n). - Muniru A Asiru, Dec 21 2018
MAPLE
a:= proc(n) 2^n + 2*n: end: seq(a(n), n=0..50); # Gary W. Adamson, Jul 20 2007
MATHEMATICA
LinearRecurrence[{4, -5, 2}, {1, 4, 8}, 34] (* Jean-François Alcover, Mar 19 2020 *)
PROG
(Magma) [2^n+2*n: n in [1..40]]; // Vincenzo Librandi, Oct 22 2011
(Maxima) makelist(2^n + 2*n, n, 0, 50); /* Franck Maminirina Ramaharo, Dec 19 2018 */
(GAP) List([0..40], n->2^n+2*n); # Muniru A Asiru, Dec 21 2018
(SageMath) [2^n +2*n for n in range(41)] # G. C. Greubel, Feb 01 2023
CROSSREFS
Cf. this sequence (m=2), A100315 (m=3), A100316 (m=4).
Row sums of A131830.
Sequence in context: A374338 A045474 A131831 * A105143 A020185 A008029
KEYWORD
nonn,easy
AUTHOR
Sergey Kitaev, Nov 13 2004
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 21 2018
STATUS
approved