A036364 Number of free n-ominoes with cell centers determining n-2 space (proper dimension n-2).

1, 4, 11, 35, 104, 319, 951, 2862, 8516, 25369, 75167, 222529, 656961, 1937393, 5704426, 16781247, 49320800, 144866243, 425263010, 1247877578, 3660478408, 10734834603, 31475111515, 92273758477, 270486112046, 792836030163, 2323835125879, 6811162237825

Offset: 3

Author

Robert A. Russell

Keywords

• easy
• nice
• nonn

Comments

Lunnon's DE(n,n-2); Lunnon's DE(n,n-1) is number of free trees.

Examples

			1 tromino in 1-space;
4 nonstraight tetrominoes in 2-space;
11 nonflat pentominoes in 3-space (chiral pairs count as one).
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 3..1000 (terms 3..200 from Vincenzo Librandi)
• W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-67.

Crossrefs

Cf. A000081, A000055, A036365, A171860 (fixed).

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, 3 ]/2+5b[ i, 4 ]/8+Sum[ b[ i, j ], {j, 5, i} ]+If[ OddQ[ i ], 0, 7b[ i/2, 2 ]/8
+If[ OddQ[ i/2 ], 0, b[ i/4, 1 ]/4 ]+Sum[ b[ i/2, j ], {j, 3, i/2} ] ]
+Sum[ b[ j, 1 ](b[ i-2j, 1 ]/2+b[ i-2j, 2 ]/4)+Sum[ If[ OddQ[ k ], b[ j,
(k-1)/2 ]b[ i-2j, 1 ], 0 ], {k, 5, i} ], {j, 1, (i-1)/2} ], {i, 3, 30} ]

Formula

G.f.: B^3(x)/2 + B(x)B(x^2)/2 + 5B^4(x)/8 + B^2(x)B(x^2)/4 + 7B^2(x^2)/8 + B(x^4)/4 + B^5(x)/(1-B(x)) + (B(x)+B(x^2))B^2(x^2)/(1-B(x^2)), where B(x) is the generating function for rooted trees with n nodes (that is, B(x) is the g.f. of sequence A000081).

a(n) ~ A340310 * A051491^n / sqrt(n). - Vaclav Kotesovec, Apr 12 2021