A045648 Number of chiral n-ominoes in (n-1)-space, one cell labeled.

1, 1, 1, 2, 4, 8, 16, 34, 75, 166, 370, 841, 1937, 4488, 10470, 24617, 58237, 138435, 330563, 792745, 1908379, 4609434, 11167781, 27134824, 66102921, 161417867, 395042562, 968791315, 2380383481, 5859176855, 14446043494, 35672895787, 88219204394, 218466647493

Offset: 1

Author

Robert A. Russell

Keywords

• easy
• nonn

Comments

Needed for generating chiral n-ominoes in (n-1)-space with no cells labeled, Lunnon's DR(n, n-1) - DE(n, n-1). Knuth describes a method for a similar enumeration, that of free trees with n nodes.

Euler transform of a(n) - if(n%4!=2, 0, a(n/2)) is sequence itself with offset 0.

References

• D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-388.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-367.

Crossrefs

Cf. A045649, A000081, A004111.

Programs

Maple

with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(d*(a(d)-
      `if`(irem(d, 4)=2, a(d/2), 0)), d=divisors(j))*b(n-j), j=1..n)/n)
    end:
a:= n-> b(n-1):
seq(a(n), n=1..40);  # Alois P. Heinz, Feb 24 2015

Mathematica

s[ n_, k_ ] := s[ n, k ]=c[ n+1-k ]+If[ n<2k, 0, s[ n-k, k ](-1)^k ]; c[ 1 ]=1; c[ n_ ] := c[ n ]=Sum[ c[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); Table[ c[ i ], {i, 1, 30} ]

PARI

{a(n)=local(A=x); if(n<1, 0, for(k=1, n-1, A/=(1-(-x)^k+x*O(x^n))^((-1)^k*polcoeff(A, k))); polcoeff(A, n))} /* Michael Somos, Dec 16 2002 */

Formula

G.f.: A(x) = x exp(A(x) + A(-x^2)/2 + A(x^3)/3 + A(-x^4)/4 + ...).

Also A(x) = Sum_{n >= 1} a(n)*x^n = x / Product_{n >= 1} (1-(-x)^n)^((-1)^n*a(n)).

G.f.: x*Product_{n>0} (1-x^(4n-2))^a(2n-1)/(1-x^n)^a(n).

a(n) ~ c * d^n / n^(3/2), where d = 2.58968405406171542574769690513208346256... and c = 0.386431095907583923297618874742... . - Vaclav Kotesovec, Feb 29 2016