A036367 Number of free orthoplex n-ominoes with cell centers determining n-2 space.

1, 2, 8, 25, 86, 272, 875, 2732, 8505, 26104, 79708, 241522, 728632, 2187951, 6548819, 19542662, 58184124, 172880565, 512837063, 1519158462, 4494920802, 13286473612, 39240530012, 115811180864, 341588823740, 1007007175952, 2967361180383

Offset: 4

Author

Robert A. Russell

Keywords

• easy
• nice
• nonn

Comments

Orthoplex polyominoes are multidimensional polyominoes that do not extend more than two units along any axis.

Examples

			a(4)=1 because there is 1 tetromino (a square) in 2^2 space;
a(5)=2 because there are 2 pentominoes in 2^3 space;
a(6)=8 because in 2^4 space there are 8 hexominoes that have cell centers determining 4-space.
		

Crossrefs

Cf. A000081, A036364.

Programs

Mathematica

sb[ n_, k_ ] := sb[ n, k ]=b[ n+1-k, 1 ]+If[ n<2k, 0, sb[ n-k, k ] ]; b[ 1, 1 ] := 1;
b[ n_, 1 ] := b[ n, 1 ]=Sum[ b[ i, 1 ]sb[ n-1, i ]i, {i, 1, n-1} ]/(n-1);
b[ n_, k_ ] := b[ n, k ]=Sum[ b[ i, 1 ]b[ n-i, k-1 ], {i, 1, n-1} ];
Table[ b[ i, 4 ]/8+Sum[ b[ i, j ], {j, 5, i} ]/2+If[ OddQ[ i ], 0, 3b[ i/2, 2 ]/8
+If[ OddQ[ i/2 ], 0, b[ i/4, 1 ]/4 ]+Sum[ b[ i/2, j ], {j, 3, i/2} ]/2 ]
+Sum[ b[ j, 1 ]b[ i-2j, 2 ]/4+Sum[ If[ OddQ[ k ], b[ j,
(k-1)/2 ]b[ i-2j, 1 ], 0 ], {k, 5, i} ]/2, {j, 1, (i-1)/2} ], {i, 4, 30} ]

Formula

G.f.: (B^2(x) + B(x^2))^2/8 + B^2(x^2)/4 + B(x^4)/4 + B^5(x)/(2 - 2*B(x)) + (B(x) + B(x^2))*B^2(x^2)/(2 - 2*B(x^2)) where B(x) is the generating function for rooted trees with n nodes in A000081.