A019537 Number of special orbits for dihedral group of degree n.

1, 2, 4, 14, 61, 414, 3416, 34274, 394009, 5113712, 73758368, 1170495180, 20263806277, 380048113202, 7676106638884, 166114210737254, 3834434327929981, 94042629562443206, 2442147034770292496, 66942194906543381336, 1931543452346146410965, 58519191359170883258606

Offset

1,2

Comments

a(n) is the number of ways to color a necklace of n beads using at most n colors. Turning the necklace over does not count as different. - Robert A. Russell, May 31 2018

Links

Table of n, a(n) for n=1..22.

M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)

Formula

a(n) = Sum_{k=1..n} ((k!/4)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/(2 n))*Sum_{d|n} phi(d)*S2(n/d,k)), where S2(n,k) is the Stirling subset number A008277. - Robert A. Russell, May 31 2018

a(n) ~ (n-1)! / (4 * log(2)^(n+1)). - Vaclav Kotesovec, Jul 21 2019

Example

For a(3) = 4, the necklaces are AAA, AAB, ABB, and ABC. Last one is chiral. For a(4) = 14, the necklacess are AAAA, AAAB, AABB, ABAB, ABBB, ABAC, ABCB, ACBC, AABC, ABBC, ABCC, ABCD, ABDC, and ACBD. Last six are chiral. - Robert A. Russell, May 31 2018

Mathematica

Table[Sum[(k!/(2n)) DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k] &] + (k!/4) (StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k]), {k, 1, n}], {n, 1, 40}] (* Robert A. Russell, May 31 2018 *)

Prog

(PARI) a(n) = sum(k=1, n, (k!/4)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)) + (k!/(2*n))*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2))); \\ Michel Marcus, Jun 06 2018

Crossrefs

Cf. A019536.

Row sums of A273891.

Sequence in context: A047009 A027740 A132880 * A046911 A089127 A132852

Adjacent sequences: A019534 A019535 A019536 * A019538 A019539 A019540

Keyword

nonn

Author

Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de)

Extensions

More terms (using A273891) from Alois P. Heinz, Jun 02 2016

Status

approved