login
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.
0
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.
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
Sequence in context: A226985 A174407 A160727 * A086508 A085641 A086516
KEYWORD
nonn,tabl
AUTHOR
Steffen Eger, Mar 06 2011
STATUS
approved