|
Search: id:A045648
|
|
|
| A045648 |
|
Number of chiral n-ominoes in (n-1)-space, one cell labeled. |
|
+0
5
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
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 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-88.
W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-67.
|
|
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 prod_{n>0} (1-x^(4n-2))^a(2n-1)/(1-x^n)^a(n).
|
|
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} ]
|
|
PROGRAM
|
(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
|
Cf. A045649, A000081, A004111.
Sequence in context: A096812 A006981 A003427 this_sequence A166354 A013025 A034339
Adjacent sequences: A045645 A045646 A045647 this_sequence A045649 A045650 A045651
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Robert A. Russell (russell(AT)post.harvard.edu)
|
|
|
Search completed in 0.002 seconds
|
