A343208 a(n) = Sum_{k=1..n} k*A001168(k)*binomial(n-1,k-1), where A001168(k) is the number of fixed polyominoes with k cells.

1, 5, 27, 143, 744, 3832, 19636, 100348, 511969, 2608905, 13282011, 67567527, 343510966, 1745495390, 8865633276, 45013599940, 228478238613, 1159398424925, 5881978415019, 29835289653043, 151308803657699, 767245632538063, 3889991549017581, 19720295705928713, 99961847384995974

Offset: 1

Author

Scott R. Shannon and Zach J. Shannon, Apr 08 2021

Keywords

• nonn

Comments

This is the number of ways n blocks can be placed on a 2D grid such that, after the first block, each block touches at least one face of a previously placed block, and each block either touches the ground plane or is supported by a block below it. See the attached file for a derivation.

The number of ways n squares can be placed similarly on a 1D line is given by A001792.

Examples

			Considering the sequence as face-touching blocks:
a(1) = 1 as a single block can be placed in one way.
a(2) = 5 as, after the first block is placed, the second block can be placed so that it touches the ground plane and one of the four sides of the first block, or it can be placed directly on top of the first block, giving five total arrangements.
a(3) = 27 as the third block can be placed in one way directly on top of the tower of the two previous blocks, on the ground next to the tower of two blocks in four ways, next to one of the three faces of the second block on the ground plane or on top of the second block in 4*4 = 16 total ways, or on the ground plane touching one of the faces of the first block with the second block touching one of the other faces of the first block in 6 total ways. Summing the configurations gives 27 total ways the three blocks can be arranged.
		

Links

• Scott R. Shannon, Derivation of the title formula.

Crossrefs

Cf. A001168, A001792, A007318.