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

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

Author

Sergey Kitaev, Nov 13 2004

Keywords

• nonn
• easy

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..2000
• Ronald Cools, Encyclopaedia of Cubature Formulas
• S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. this sequence (m=2), A100315 (m=3), A100316 (m=4).

Cf. A000051, A000079, A001787, A002064, A005126, A005843.

Cf. A052548, A058331, A099003, A132750, A176691.

Row sums of A131830.

Programs

GAP

List([0..40],n->2^n+2*n); # Muniru A Asiru, Dec 21 2018

Magma

[2^n+2*n: n in [1..40]]; // Vincenzo Librandi, Oct 22 2011

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 *)

Maxima

makelist(2^n + 2*n, n, 0, 50); /* Franck Maminirina Ramaharo, Dec 19 2018 */

SageMath

[2^n +2*n for n in range(41)] # G. C. Greubel, Feb 01 2023

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

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 21 2018