A033505 -id:A033505 - cp's OEIS frontend

A187152 Triangle T(m,n), read by rows: Number of bipartite labeled graphs (V,E) with vertices A={a_1,...,a_m} and B={b_1,...,b_n} where for any vertex in V at most one edge in E is allowed. Additionally, an edge {a_k,b_l} is allowed only when |k-l|<=1.

2, 3, 7, 3, 10, 22, 3, 10, 32, 71, 3, 10, 32, 103, 228, 3, 10, 32, 103, 331, 733, 3, 10, 32, 103, 331, 1064, 2356, 3, 10, 32, 103, 331, 1064, 3420, 7573, 3, 10, 32, 103, 331, 1064, 3420, 10993, 24342, 3, 10, 32, 103, 331, 1064, 3420, 10993, 35335, 78243

Offset: 1

Steffen Eger, Mar 06 2011

This also has the obvious corresponding string alignment interpretation where we allow only one-to-one alignments between strings a_1...a_m and b_1...b_n, and additionally demand that aligned characters have a distance of at most 1.

			2;
3 7;
3 10 22;
3 10 32 71;
3 10 32 103 228;
3 10 32 103 331 733;
3 10 32 103 331 1064 2356;
3 10 32 103 331 1064 3420 7573;
3 10 32 103 331 1064 3420 10993 24342;
3 10 32 103 331 1064 3420 10993 35335 78243;
3 10 32 103 331 1064 3420 10993 35335 113578 251498;

Cf. A033505, A030186.

For m >= n:
T(m,n) =
   A030186(m)   if m = n
   A033505(n+1) if m >= n+1
Symmetrically extended by T(n,m)=T(m,n).
Both the diagonal and the off-diagonals follow the recurrence a(n) = 3*a(n-1) + a(n-2) - a(n-3), n >= 3, with different initial conditions; 2,7,22 and 3,10,32, respectively.

A386489 Expansion of (1-x)/((1+x+2x^2)(1-4*x+x^2)).

Original entry on oeis.org

1, 2, 7, 30, 109, 402, 1511, 5638, 21021, 78474, 292887, 1093006, 4079181, 15223810, 56815879, 212039702, 791343293, 2953333114, 11021988791, 41134623134, 153516503405, 572931388658, 2138209053735, 7979904827430, 29781410249821, 111145736175722

Offset: 0

Greg Dresden and Madison Lingchen Zhou, Aug 20 2025

a(n) is the number of ways to tile a 2 X n board with squares, dominoes, and L-shaped quadrominoes. Here is one of the a(4)=109 possible tilings of a 2 X 4 board:
    _____
   | | |||
   ||____|
Compare to A030186 which counts the tilings with just squares and dominos.

Index entries for linear recurrences with constant coefficients, signature (3,1,7,-2).

Cf. A030186, A033505.

LinearRecurrence[{3, 1, 7, -2}, {1, 2, 7, 30}, 30]

a(n) = 3*a(n-1) + a(n-2) + 7*a(n-3) - 2*a(n-4).
a(n) = A030186(n) + 2*sum_{i=0..n-2}(A033505(n-i-3)*a(i) + A030186(n-i-3)*(a(i)+2*sum_{j=0..i} a(j)).
a(n) ~ (2 + sqrt(3))^(n+2) / (18 + 4*sqrt(3)). - Vaclav Kotesovec, Aug 21 2025
23*a(n) = -4*A001353(n)+13*A001353(n+1) +10*A001607(n+1)+8*A001607(n) . - R. J. Mathar, Aug 26 2025

cp's OEIS Frontend

A187152 Triangle T(m,n), read by rows: Number of bipartite labeled graphs (V,E) with vertices A={a_1,...,a_m} and B={b_1,...,b_n} where for any vertex in V at most one edge in E is allowed. Additionally, an edge {a_k,b_l} is allowed only when |k-l|<=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A386489 Expansion of (1-x)/((1+x+2x^2)(1-4*x+x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

cp's OEIS Frontend

A187152 Triangle T(m,n), read by rows: Number of bipartite labeled graphs (V,E) with vertices A={a_1,...,a_m} and B={b_1,...,b_n} where for any vertex in V at most one edge in E is allowed. Additionally, an edge {a_k,b_l} is allowed only when |k-l|<=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A386489 Expansion of (1-x)/((1+x+2*x^2)*(1-4*x+x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A386489 Expansion of (1-x)/((1+x+2x^2)(1-4*x+x^2)).