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,1

Comments

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.

Links

Table of n, a(n) for n=1..55.

Formula

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.

Example

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;

Crossrefs

Cf. A033505, A030186.

Sequence in context: A226985 A174407 A160727 * A086508 A085641 A086516

Adjacent sequences: A187149 A187150 A187151 * A187153 A187154 A187155

Keyword

nonn,tabl

Author

Steffen Eger, Mar 06 2011

Status

approved