login
A045648
Number of chiral n-ominoes in (n-1)-space, one cell labeled.
20
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,4
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
W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-367.
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
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} ]
PROG
(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 */
CROSSREFS
KEYWORD
easy,nonn
STATUS
approved