A338531 a(n) is the number of row-convex domino towers with n bricks (rows need not be offset).

1, 4, 16, 61, 225, 815, 2923, 10428, 37097, 131776, 467732, 1659537, 5886945, 20880912, 74060619, 262672473, 931615218, 3304121816, 11718561425, 41561571533

Offset: 1

Author

Alexander M. Haupt, Nov 01 2020

Keywords

• nonn
• more

Comments

A domino tower is a stack of bricks, where (1) the bottom row is contiguous, and (2) each brick is supported from below by at least half of a brick. Note, that in this definition of domino towers, rows need not be offset by half a brick. The number of domino towers with n bricks is given by 4^(n-1).

In this sequence we want all rows to be convex, rather than just the bottom row.

Examples

			For n=2, the a(2) = 4 domino towers are:
+-------+-------+
|       |       |
+-------+-------+
+-------+
|       |
+---+---+---+
    |       |
    +-------+
+-------+
|       |
+-------+
|       |
+-------+
    +-------+
    |       |
+---+---+---+
|       |
+-------+
For n=4, the 4^(n-1)-a(n)=64-61=3 domino towers, which have non-convex rows are:
+-------+   +-------+
|       |   |       |
+-------+---+---+---+
|       |       |
+-------+-------+
+-------+   +-------+
|       |   |       |
+---+---+---+-------+
    |       |       |
    +-------+-------+
+-------+       +-------+
|       |       |       |
+---+---+---+---+---+---+
    |       |       |
    +-------+-------+
		

Links

• T. M. Brown, Convex domino towers, J. of Integer Sequences, 20 (2017), p.17.

Crossrefs

Cf. A275204.

Programs

Mathematica

f[n_, l_] := (f[n, l] =
Sum[(3 - 2 i + 2 l) f[n - i, i], {i, 1, Min[n, l + 1]}]);
f[0, l_] := 1;
Table[Sum[f[n - l, l], {l, 1, n}], {n, 1, 20}]

Formula

G.f.: G(x) := [ Sum_{l>0} z^l (z^3 T(3,l)+(2 z^2-1) T(2,l)+(2 z+1) T(1,l)) ] / (z^5 T(2,3)+(3 z-1) z^3 T(1,3)+(4 z^3-3 (z+1) z+1) T(1,2)) , where

T(i,j) := A(i)B(j)-A(j)B(i),

A(l) := Sum_{n>=0} (z^(l n+n^2+n) (-z;z)_n)/((z;z)_n)^2,

B(l) := Sum_{n>=0} (z^(l n+n^2+n) (-z;z)n)/((z;z)_n)^2 * (l+n+Sum{m=1,...,n} (3 z^m+1)/(1-z^(2 m))), and

(a;q)_n is the q-Pochhammer symbol