A320314 a(n) is the number of symmetric domino towers with n bricks.

1, 1, 3, 3, 7, 9, 19, 25, 53, 71, 149, 203, 423, 583, 1209, 1681, 3473, 4863, 10017, 14107, 28987, 41019, 84113, 119513, 244645, 348829, 712987, 1019731, 2081547, 2985097, 6086375, 8749185, 17820657, 25671983, 52241825, 75402907, 153316715, 221673707, 450393329, 652234089

Offset: 1

Author

Peter Kagey, Oct 10 2018

Keywords

• nonn

Comments

A domino tower is a stack of bricks, where (1) each row is offset from the preceding row by half of a brick, (2) the bottom row is contiguous, and (3) each brick is supported from below by at least half of a brick.

The number of (not necessarily symmetric) domino towers with n blocks is given by 3^(n-1).

a(n) is odd for all n.

The not necessarily symmetric case is described in the Miklos Bona reference. Similar considerations lead to a decomposition of symmetric towers into half pyramids which are enumerated by the Motzkin numbers. - Andrew Howroyd, Mar 12 2021

Examples

			For n = 4, the a(4) = 3 symmetric stacks are
    +-------+
    |       |
+---+---+---+---+
|       |       |
+---+---+---+---+,
    |       |
    +-------+
+-------+       +-------+
|       |       |       |
+---+---+---+---+---+---+, and
    |       |       |
    +-------+-------+
+-------+-------+-------+-------+
|       |       |       |       |
+-------+-------+-------+-------+.
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 25-27.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Peter Kagey, Symmetric Brick Stacking, Mathematics Stack Exchange.

Crossrefs

Cf. A000244, A001006, A168368, A264746.

Programs

PARI

seq(n)={my(h=(1 - x^2 - sqrt(1-2*x^2-3*x^4 + O(x^3*x^n)))/(2*x^2)); Vec((x + 2*x*h + h)/((1-x*h)*(1-h)))} \\ Andrew Howroyd, Mar 12 2021

Formula

G.f.: (x + 2*x^3*M(x^2) + x^2*M(x^2))/((1-x^3*M(x^2))*(1-x^2*M(x^2))) where M(x) is the g.f. of A001006. - Andrew Howroyd, Mar 12 2021

Extensions

a(20)-a(40) from Andrew Howroyd, Oct 25 2018