Symmetric Brick Stacking

Suppose you stack $$n$$ LEGO bricks ($$2 \times 1$$) in a plane, where

• The base is contiguous
• Each level is offset from the level below it by one stud.
• Bricks are only stacked on top of other bricks, not below.

It turns out that there are exactly $$3^{n-1}$$ such stacks. (See here beginning on page 25.)

Question

How many such stacks are left-right symmetric? By my brute force program:

n  | # symmetric stacks
---+-------------------
1  | 1
2  | 1
3  | 3
4  | 3
5  | 7
6  | 9
7  | 19
8  | 25
9  | 53
10 | 71
11 | 149
12 | 203
13 | 423
14 | 583
15 | 1209


And by a parity argument, there are an odd number of such stacks for each value of $$n$$.

Examples

For example, the following three stacks of four bricks are legal:

Non-Examples

The following three stacks are not legal because they violate the three conditions above: in the first, the base is not contiguous; in the second, the levels are not offset; and in the third, the second brick in the second row doesn't have any bricks below it.

• This is extremely similar to a Project Euler Problem Oct 9, 2018 at 21:12
• My other question is loosely related. Oct 9, 2018 at 21:13
• @RushabhMehta, can you find which problem? Perhaps Problem 215? Oct 9, 2018 at 21:13
• Oops, this is not nearly as similar as I remember it to be. My bad. Here is the problem. Oct 9, 2018 at 21:16
• I've submitted this to the OEIS as A320314. Right now it's a draft, but I expect it will be added as a sequence within a few days. Oct 10, 2018 at 20:23