A045649 -id:A045649 - cp's OEIS frontend

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

Robert A. Russell

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.

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

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.

Cf. A045649, A000081, A004111.

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

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} ]

{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 */

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

A195738 Triangle read by rows: DR(n,d) is the number of properly d-dimensional polyominoes with n cells, modulo translations and rotations (n >= 1, 0 <= d <= n-1).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 6, 3, 0, 1, 17, 17, 4, 0, 1, 59, 131, 52, 7, 0, 1, 195, 915, 709, 153, 13, 0, 1, 703, 6553, 8946, 3350, 454, 28

Offset: 1

N. J. A. Sloane, Sep 22 2011

From Petros Hadjicostas, Jan 11 2019: (Start)
Table 1 (p. 366) in Lunnon (1975) contains more terms. Because the table there (in the reference) has incomplete columns, the extra terms do not appear in this triangular sequence (array).
Entry DR(n=11, d=2) in Table 1 (p. 366) must be a typo. It should not be 33890, but 33895. This was corrected by N. J. A. Sloane in 2011 in the documentation of sequence A006758. (See also sequence A000988.)
(End)
The number of oriented polyominoes (chiral pairs counted as two) here is the sum of the number of unoriented polyominoes (chiral pairs counted as one) in A049430 and the number of chiral pairs. - Robert A. Russell, May 03 2020

			Triangle begins:
n\d| 0    1    2    3    4    5    6    7
---+---------------------------------=---
1  | 1
2  | 0    1
3  | 0    1    1
4  | 0    1    6    3
5  | 0    1   17   17    4
6  | 0    1   59  131   52    7
7  | 0    1  195  915  709  153   13
8  | 0    1  703 6553 8946 3350  454   28
...

W. F. Lunnon, Counting multidimensional polyominoes, Computer Journal 18 (4) (1975) 366-367.

Columns give A006758 (and A000988), A006759, A006760, A006761.
Cf. A195739, A049430.
Cf. A000055, A045649, A036364, A036365.

From Robert A. Russell, May 03 2020: (Start)
For n > 1, DR(n,n-1) = A000055(n) + A045649(n).
DR(n,n-2) = A036364(n) + A036365(n).
We can add unoriented and chiral pairs for the top two diagonals. The summands have quick algorithms. (End)

Sequence corrected by Petros Hadjicostas, Jan 11 2019 after observation by Jon E. Schoenfield

A355049 Number of chiral pairs of orthoplex n-ominoes with cell centers determining n-3 space.

Original entry on oeis.org

8, 76, 440, 2019, 8147, 30367, 107061, 361655, 1181761, 3762817, 11733393, 35957132, 108591703, 323914688, 955984083, 2795513143, 8108894051, 23354358683, 66838785954, 190211189706, 538567451991, 1517943035326

Offset: 7

Robert A. Russell, Jun 16 2022

Orthoplex polyominoes are connected sets of cells of regular tilings with Schläfli symbols {}, {4}, {3,4}, {3,3,4}, {3,3,3,4}, etc. These are tilings of regular orthoplexes projected on their circumspheres. Orthoplex polyominoes are equivalent to multidimensional polyominoes that do not extend more than two units along any axis, i.e., fit within a 2^d cube. Each member of a chiral pair is a reflection but not a rotation of the other.

			a(7)=8 because there are 8 pairs of chiral heptominoes in 2^4 space. See trunks 1, 6, 8, 12, 13, 19, 27, and 28 in the linked Trunk Generating Functions.

Robert A. Russell, Table of n, a(n) for n = 7..100
Robert A. Russell, Trunk Generating Functions

Cf. A355047 (oriented), A355048 (unoriented), A355050 (achiral) A355051 (asymmetric), A045648 (rooted chiral).

Other dimensions: A036368 (n-2), A045649 (n-1), A355054 (multidimensional).

sc[n_,k_] := sc[n,k] = c[n+1-k,1] + If[n<2k, 0, sc[n-k,k](-1)^k];
c[1,1] := 1; c[n_,1] := c[n,1] = Sum[c[i,1] sc[n-1,i]i, {i,1,n-1}]/(n-1);
c[n_,k_] := c[n, k] = Sum[c[i, 1] c[n-i, k-1], {i,1,n-1}];
nmax = 30; K[x_] := Sum[c[i,1] x^i, {i,0,nmax}]
Drop[CoefficientList[Series[(14 K[x]^6 + 3 K[x]^7 + 6 K[x]^4 K[-x^2] + 6 K[x]^5 K[-x^2] - 18 K[x]^2 K[-x^2]^2 + 3 K[x]^3 K[-x^2]^2 - 10 K[-x^2]^3 - 6 K[x] K[-x^2]^3 + 4 K[x^3]^2 - 6 K[x] K[-x^2] K[-x^4] + 4 K[-x^6]) / 24 + K[x]^3 (38 K[x]^4 + 9 K[x]^5 + 4 K[x]^2 K[-x^2] + 10 K[x]^3 K[-x^2] - 2 K[-x^2]^2 + K[x] K[-x^2]^2) / (8(1-K[x])) + K[x]^6 (5 K[x] + 16 K[x]^2 + 6 K[x]^3 + K[-x^2] + 2 K[x] K[-x^2]) / (2(1-K[x])^2) - K[-x^2]^2 (K[x]^4 + 2 K[x] K[-x^2] + 4 K[x]^2 K[-x^2] + 2 K[-x^2]^2 + 5 K[x] K[-x^2]^2 + K[-x^4] + K[x] K[-x^4]) / (4(1-K[-x^2])) + K[x]^7 (2 + 42 K[x] + 51 K[x]^2 + 24 K[x]^3 + 3 K[-x^2]) / (12(1-K[x])^3) + (K[x] K[x^3]^2) / (3(1-K[x^3])) - K[x]^2 K[-x^2]^2 (2 K[x] + 5 K[x]^3 + 2 K[-x^2] + K[x] K[-x^2]) / (4(1-K[x]) (1-K[-x^2])) - K[-x^2]^4 (8 + K[x] + 8 K[x] K[-x^2]) / (8(1-K[-x^2])^2) + K[x]^9 (17 + 8 K[x]) / (8(1-K[x])^4) - K[x]^5 (1 + 4 K[x]) K[-x^2]^2 / (4(1-K[x])^2 (1-K[-x^2])) + (K[x] K[-x^4]^2) / (4(1-K[-x^4])) + (3 K[x]^10) / (8(1-K[x])^5) - ((K[x]^6 K[-x^2]^2) / (4(1-K[x])^3 (1-K[-x^2]))) - (((1 + K[x]) K[-x^2]^5) / (4(1-K[-x^2])^3)) + ((1 + K[x]) K[-x^2] K[-x^4]^2) / (4(1-K[-x^2]) (1-K[-x^4])) - ((K[x]^2 K[-x^2]^4) / (8(1-K[x]) (1-K[-x^2])^2)), {x,0,nmax}], x], 7]

a(n) = A355047(n) - A355048(n) = (A355047(n) - A355050(n)) / 2 = A355048(n) - A355050(n).

G.f.: (14 C(x)^6 + 3 C(x)^7 + 6 C(x)^4 C(-x^2) + 6 C(x)^5 C(-x^2) - 18 C(x)^2 C(-x^2)^2 + 3 C(x)^3 C(-x^2)^2 - 10 C(-x^2)^3 - 6 C(x) C(-x^2)^3 + 4 C(x^3)^2 - 6 C(x) C(-x^2) C(-x^4) + 4 C(-x^6)) / 24 + C(x)^3 (38 C(x)^4 + 9 C(x)^5 + 4 C(x)^2 C(-x^2) + 10 C(x)^3 C(-x^2) - 2 C(-x^2)^2 + C(x) C(-x^2)^2) / (8(1-C(x))) + C(x)^6 (5 C(x) + 16 C(x)^2 + 6 C(x)^3 + C(-x^2) + 2 C(x) C(-x^2)) / (2(1-C(x))^2) - C(-x^2)^2 (C(x)^4 + 2 C(x) C(-x^2) + 4 C(x)^2 C(-x^2) + 2 C(-x^2)^2 + 5 C(x) C(-x^2)^2 + C(-x^4) + C(x) C(-x^4)) / (4(1-C(-x^2))) + C(x)^7 (2 + 42 C(x) + 51 C(x)^2 + 24 C(x)^3 + 3 C(-x^2)) / (12(1-C(x))^3) + (C(x) C(x^3)^2) / (3(1-C(x^3))) - C(x)^2 C(-x^2)^2 (2 C(x) + 5 C(x)^3 + 2 C(-x^2) + C(x) C(-x^2)) / (4(1-C(x)) (1-C(-x^2))) - C(-x^2)^4 (8 + C(x) + 8 C(x) C(-x^2)) / (8(1-C(-x^2))^2) + C(x)^9 (17 + 8 C(x)) / (8(1-C(x))^4) - C(x)^5 (1 + 4 C(x)) C(-x^2)^2 / (4(1-C(x))^2 (1-C(-x^2))) + (C(x) C(-x^4)^2) / (4(1-C(-x^4))) + (3 C(x)^10) / (8(1-C(x))^5) - ((C(x)^6 C(-x^2)^2) / (4(1-C(x))^3 (1-C(-x^2)))) - (((1 + C(x)) C(-x^2)^5) / (4(1-C(-x^2))^3)) + ((1 + C(x)) C(-x^2) C(-x^4)^2) / (4(1-C(-x^2)) (1-C(-x^4))) - ((C(x)^2 C(-x^2)^4) / (8(1-C(x)) (1-C(-x^2))^2)) where C(x) is the generating function for chiral n-ominoes in n-1 space, one cell labeled in A045648.

A355054 Number of chiral pairs of multidimensional n-ominoes with cell centers determining n-3 space.

Original entry on oeis.org

6, 54, 297, 1341, 5468, 20519, 72168, 242886, 791780, 2514453, 7814225, 23863941, 71835845, 213601046, 628450974, 1832227629, 5299559865, 15221688836, 43450246045, 123345029035, 348417524877, 979803281560

Offset: 5

Robert A. Russell, Jun 16 2022

Multidimensional polyominoes are connected sets of cells of regular tilings with Schläfli symbols {oo}, {4,4}, {4,3,4}, {4,3,3,4}, etc. Each tile is a regular orthotope (hypercube). Each member of a chiral pair is a reflection but not a rotation of the other.

			a(5)=6 because there are 6 chiral pairs of pentominoes in 2-space.

Robert A. Russell, Table of n, a(n) for n = 5..100
W. F. Lunnon, Counting multidimensional polyominoes. Computer Journal 18 (1975), no. 4, pp. 366-367.
Robert A. Russell, Trunk Generating Functions

Cf. A355052 (oriented), A355053 (unoriented), A355055 (achiral) A355056 (asymmetric), A191092 (fixed), A045648 (rooted chiral), A195738 (Lunnon's DR), A049430 (Lunnon's DE).

Other dimensions: A036365 (n-2), A045649 (n-1), A355049 (orthoplex).

sc[n_,k_] := sc[n,k] = c[n+1-k,1] + If[n<2k, 0, sc[n-k,k](-1)^k];
c[1,1] := 1; c[n_,1] := c[n,1] = Sum[c[i,1] sc[n-1,i]i, {i,1,n-1}]/(n-1);
c[n_,k_] := c[n, k] = Sum[c[i, 1] c[n-i, k-1], {i,1,n-1}];
nmax = 30; K[x_] := Sum[c[i,1] x^i, {i,0,nmax}]
Drop[CoefficientList[Series[(12 K[x]^4 + 87 K[x]^5 + 50 K[x]^6 + 3 K[x]^7 + 18 K[x]^3 K[-x^2] + 36 K[x]^4 K[-x^2] + 6 K[x]^5 K[-x^2] - 12 K[-x^2]^2 - 27 K[x] K[-x^2]^2 - 6 K[x]^2 K[-x^2]^2 + 3 K[x]^3 K[-x^2]^2 - 16 K[-x^2]^3 - 6 K[x] K[-x^2]^3 + 4 K[x^3]^2 - 6 K[x] K[-x^4] - 6 K[x] K[-x^2] K[-x^4] + 4 K[-x^6]) / 24 + K[x]^2 (16 K[x]^3 + 159 K[x]^4 + 112 K[x]^5 + 9 K[x]^6 + 14 K[x]^2 K[-x^2] + 32 K[x]^3 K[-x^2] + 10 K[x]^4 K[-x^2] - K[-x^2]^2 + K[x]^2 K[-x^2]^2) / (8 (1-K[x])) + K[x]^5 (2 K[x] + 67 K[x]^2 + 46 K[x]^3 + 6 K[x]^4 + 3 K[-x^2] + 6 K[x] K[-x^2] + 2 K[x]^2 K[-x^2]) / (2 (1-K[x])^2) - K[-x^2] (2 K[x]^2 K[-x^2] + 7 K[-x^2]^2 + 17 K[x] K[-x^2]^2 + 2 K[x]^2 K[-x^2]^2 + 7 K[-x^2]^3 + 5 K[x] K[-x^2]^3 + K[-x^4] + K[x] K[-x^4] + K[-x^2] K[-x^4] + K[x] K[-x^2] K[-x^4]) / (4 (1-K[-x^2])) + K[x]^6 (4 K[x] + 153 K[x]^2 + 75 K[x]^3 + 12 K[x]^4 + 3 K[-x^2] + 3 K[x] K[-x^2]) / (6 (1-K[x])^3) - K[x]^2 K[-x^2]^2 (K[x] + K[-x^2]) / ((1-K[x]) (1-K[-x^2])) + (K[x] K[x^3]^2) / (3 (1-K[x^3])) + K[x]^9 (21 + 4 K[x]) / (2 (1-K[x])^4) - K[-x^2]^4 (6 + 7 K[x] + 2 K[-x^2] + 2 K[x] K[-x^2]) / (2 (1-K[-x^2])^2) + 3 K[x]^10 / (2 (1-K[x])^5) - K[x]^2 K[-x^2]^4 / (2 (1-K[x]) (1-K[-x^2])^2) - (1 + K[x]) K[-x^2]^5 / (1-K[-x^2])^3, {x,0,nmax}], x], 5]

a(n) = A355052(n) - A355053(n) = (A355052(n) - A355055(n)) / 2 = A355053(n) - A355055(n).
a(n) = A195738(n,n-3) - A049430(n,n-3), diagonals of Lunnon's DR and DE arrays.
G.f.: (12 C(x)^4 + 87 C(x)^5 + 50 C(x)^6 + 3 C(x)^7 + 18 C(x)^3 C(-x^2) + 36 C(x)^4 C(-x^2) + 6 C(x)^5 C(-x^2) - 12 C(-x^2)^2 - 27 C(x) C(-x^2)^2 - 6 C(x)^2 C(-x^2)^2 + 3 C(x)^3 C(-x^2)^2 - 16 C(-x^2)^3 - 6 C(x) C(-x^2)^3 + 4 C(x^3)^2 - 6 C(x) C(-x^4) - 6 C(x) C(-x^2) C(-x^4) + 4 C(-x^6)) / 24 + C(x)^2 (16 C(x)^3 + 159 C(x)^4 + 112 C(x)^5 + 9 C(x)^6 + 14 C(x)^2 C(-x^2) + 32 C(x)^3 C(-x^2) + 10 C(x)^4 C(-x^2) - C(-x^2)^2 + C(x)^2 C(-x^2)^2) / (8 (1-C(x))) + C(x)^5 (2 C(x) + 67 C(x)^2 + 46 C(x)^3 + 6 C(x)^4 + 3 C(-x^2) + 6 C(x) C(-x^2) + 2 C(x)^2 C(-x^2)) / (2 (1-C(x))^2) - C(-x^2) (2 C(x)^2 C(-x^2) + 7 C(-x^2)^2 + 17 C(x) C(-x^2)^2 + 2 C(x)^2 C(-x^2)^2 + 7 C(-x^2)^3 + 5 C(x) C(-x^2)^3 + C(-x^4) + C(x) C(-x^4) + C(-x^2) C(-x^4) + C(x) C(-x^2) C(-x^4)) / (4 (1-C(-x^2))) + C(x)^6 (4 C(x) + 153 C(x)^2 + 75 C(x)^3 + 12 C(x)^4 + 3 C(-x^2) + 3 C(x) C(-x^2)) / (6 (1-C(x))^3) - C(x)^2 C(-x^2)^2 (C(x) + C(-x^2)) / ((1-C(x)) (1-C(-x^2))) + (C(x) C(x^3)^2) / (3 (1-C(x^3))) + C(x)^9 (21 + 4 C(x)) / (2 (1-C(x))^4) - C(-x^2)^4 (6 + 7 C(x) + 2 C(-x^2) + 2 C(x) C(-x^2)) / (2 (1-C(-x^2))^2) + 3 C(x)^10 / (2 (1-C(x))^5) - C(x)^2 C(-x^2)^4 / (2 (1-C(x)) (1-C(-x^2))^2) - (1 + C(x)) C(-x^2)^5 / (1-C(-x^2))^3 where C(x) is the generating function for chiral n-ominoes in n-1 space, one cell labeled in A045648.

A036365 Number of chiral n-ominoes in n-2 space.

Original entry on oeis.org

0, 2, 6, 17, 49, 135, 361, 951, 2493, 6497, 16837, 43498, 112164, 288741, 742294, 1906552, 4893835, 12555662, 32201344, 82566738, 211675672, 542621858, 1390929877, 3565435302, 9139718572, 23430209922, 60069035611, 154014868677

Offset: 3

Robert A. Russell

a(n) is Lunnon's DR(n,n-2) - DE(n,n-2).

			0 chiral trominoes in 1-space;
2 pairs of chiral tetrominoes (L,S) in 2-space;
6 pairs of chiral pentominoes in 3-space.

W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-67.

Cf. A045648, A045649, A036364.

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

G.f.: C^3(x)/2 + C(x)C(-x^2)/2 + 5C^4(x)/8 + C^2(x)C(-x^2)/4 + 3C^2(-x^2)/8 - C(-x^4)/4 + C^5(x)/(1-C(x)), where C(x) is the generating function for chiral n-ominoes in n-1 space, one cell labeled (that is, C(x) is the g.f. of the sequence A045648).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A195738 Triangle read by rows: DR(n,d) is the number of properly d-dimensional polyominoes with n cells, modulo translations and rotations (n >= 1, 0 <= d <= n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A355049 Number of chiral pairs of orthoplex n-ominoes with cell centers determining n-3 space.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A355054 Number of chiral pairs of multidimensional n-ominoes with cell centers determining n-3 space.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A036365 Number of chiral n-ominoes in n-2 space.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula