A019537 - OEIS

%I #24 Jul 21 2019 03:59:57

%S 1,2,4,14,61,414,3416,34274,394009,5113712,73758368,1170495180,

%T 20263806277,380048113202,7676106638884,166114210737254,

%U 3834434327929981,94042629562443206,2442147034770292496,66942194906543381336,1931543452346146410965,58519191359170883258606

%N Number of special orbits for dihedral group of degree n.

%C 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

%H M. Goebel, <a href="http://www.informatik.uni-trier.de/~ley/db/journals/aaecc/aaecc8.html">On the number of special permutation-invariant orbits and terms</a>, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)

%F 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

%F a(n) ~ (n-1)! / (4 * log(2)^(n+1)). - _Vaclav Kotesovec_, Jul 21 2019

%e 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

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

%o (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

%Y Cf. A019536.

%Y Row sums of A273891.

%K nonn

%O 1,2

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

%E More terms (using A273891) from _Alois P. Heinz_, Jun 02 2016