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

Author

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

Keywords

• nonn

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

Examples

			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
		

Links

• 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.)

Crossrefs

Cf. A019536.

Row sums of A273891.

Programs

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 *)

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

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

Extensions

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