Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #44 Sep 11 2022 09:29:27
%S 1,3,11,70,629,7826,117655,2097684,43046889,1000010044,25937424611,
%T 743008623292,23298085122493,793714780783770,29192926025492783,
%U 1152921504875290696,48661191875666868497,2185911559749720272442,104127350297911241532859
%N Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).
%C Diagonal of arrays defined in A054630 and A054631.
%C Given n colors, a(n) = number of necklaces with n beads and 1 up to n colors effectively assigned to them (super_labeled: which also generates n different monochrome necklaces). - _Wouter Meeussen_, Aug 09 2002
%C Number of endofunctions on a set with n objects up to cyclic permutation (rotation). E.g., for n = 3, the 11 endofunctions are 1,1,1; 2,2,2; 3,3,3; 1,1,2; 1,2,2; 1,1,3; 1,3,3; 2,2,3; 2,3,3; 1,2,3; and 1,3,2. - _Franklin T. Adams-Watters_, Jan 17 2007
%C Also number of pre-necklaces in Sigma(n,n) (see Ruskey and others). - _Peter Luschny_, Aug 12 2012
%C From _Olivier Gérard_, Aug 01 2016: (Start)
%C Decomposition of the endofunctions by class size.
%C .
%C n | 1 2 3 4 5 6 7
%C --+----------------------------------
%C 1 | 1
%C 2 | 2 1
%C 3 | 3 0 8
%C 4 | 4 6 0 60
%C 5 | 5 0 0 0 624
%C 6 | 6 15 70 0 0 7735
%C 7 | 7 0 0 0 0 0 117648
%C .
%C The right diagonal gives the number of Lyndon Words or aperiodic necklaces, A075147. By multiplying each column by the corresponding size and summing, one gets A000312.
%C (End)
%D D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, 7.2.1.1. Addison-Wesley, 2005.
%H Alois P. Heinz, <a href="/A056665/b056665.txt">Table of n, a(n) for n = 1..200</a>
%H M. A. Harrison and R. G. High, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80008-0">On the cycle index of a product of permutation groups</a>, J. Combin. Theory, 4 (1968), 277-299.
%H F. Ruskey, C. Savage, and T. M. Y. Wang, <a href="http://dx.doi.org/10.1016/0196-6774(92)90047-G">Generating necklaces</a>, Journal of Algorithms, 13(3), 414 - 430, 1992.
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F a(n) = Sum_{d|n} phi(d)*n^(n/d)/n.
%F a(n) ~ n^(n-1). - _Vaclav Kotesovec_, Sep 11 2014
%F a(n) = (1/n) * Sum_{k=1..n} n^gcd(k,n). - _Joerg Arndt_, Mar 19 2017
%F a(n) = [x^n] -Sum_{k>=1} phi(k)*log(1 - n*x^k)/k. - _Ilya Gutkovskiy_, Mar 21 2018
%F From _Richard L. Ollerton_, May 07 2021: (Start)
%F a(n) = (1/n)*Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
%F a(n) = (1/n)*A228640(n). (End)
%e The 11 necklaces for n=3 are (grouped by partition of 3): (RRR,GGG,BBB),(RRG,RGG, RRB,RBB, GGB,GBB), (RGB,RBG).
%p with(numtheory):
%p a:= n-> add(phi(d)*n^(n/d), d=divisors(n))/n:
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jun 18 2013
%t Table[Fold[ #1+EulerPhi[ #2] n^(n/#2)&, 0, Divisors[n]]/n, {n, 7}]
%o (Sage)
%o # This algorithm counts all n-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime. It is algorithm F in Knuth 7.2.1.1.
%o def A056665_list(n):
%o C = []
%o for m in (1..n):
%o a = [0]*(n+1); a[0]=-1;
%o j = 1; count = 0
%o while(true):
%o if m%j == 0 : count += 1;
%o j = n
%o while a[j] >= m-1 : j -= 1
%o if j == 0 : break
%o a[j] += 1
%o for k in (j+1..n): a[k] = a[k-j]
%o C.append(count)
%o return C
%o (Sage)
%o def A056665(n): return sum(euler_phi(d)*n^(n//d)//n for d in divisors(n))
%o [A056665(n) for n in (1..18)] # _Peter Luschny_, Aug 12 2012
%o (PARI) a(n) = sum(k=1,n,n^gcd(k,n)) / n; \\ _Joerg Arndt_, Mar 19 2017
%Y Cf. A001323, A001324, A001372, A000312.
%Y Diagonal of arrays defined in A054630, A054631 and A075195.
%Y Cf. A075147 Aperiodic necklaces, a subset of this sequence.
%Y Cf. A000169 Classes under translation mod n
%Y Cf. A168658 Classes under complement to n+1
%Y Cf. A130293 Classes under translation and rotation
%Y Cf. A081721 Classes under rotation and reversal
%Y Cf. A275549 Classes under reversal
%Y Cf. A275550 Classes under reversal and complement
%Y Cf. A275551 Classes under translation and reversal
%Y Cf. A275552 Classes under translation and complement
%Y Cf. A275553 Classes under translation, complement and reversal
%Y Cf. A275554 Classes under translation, rotation and complement
%Y Cf. A275555 Classes under translation, rotation and reversal
%Y Cf. A275556 Classes under translation, rotation, complement and reversal
%Y Cf. A275557 Classes under rotation and complement
%Y Cf. A275558 Classes under rotation, complement and reversal
%Y Cf. A228640.
%K easy,nonn
%O 1,2
%A _Vladeta Jovovic_, Aug 09 2000