# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a075195
Showing 1-1 of 1
%I A075195 #87 May 10 2021 15:34:53
%S A075195 1,2,1,3,3,1,4,6,4,1,5,10,11,6,1,6,15,24,24,8,1,7,21,45,70,51,14,1,8,
%T A075195 28,76,165,208,130,20,1,9,36,119,336,629,700,315,36,1,10,45,176,616,
%U A075195 1560,2635,2344,834,60,1,11,55,249,1044,3367,7826,11165,8230,2195,108,1
%N A075195 Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.
%C A075195 From _Richard L. Ollerton_, May 07 2021: (Start)
%C A075195 Here, as in A000031, turning over is not allowed.
%C A075195 (1/n) * Dirichlet convolution of phi(n) and k^n. (End)
%D A075195 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 86 (2.2.23).
%D A075195 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 496.
%D A075195 Louis Comtet, Analyse combinatoire, Tome 2, p. 104 #17, P.U.F., 1970.
%H A075195 Andrew Howroyd, Table of n, a(n) for n = 1..1275
%H A075195 E. Jablonski, Théorie des permutations et des arrangements complets, Journal de Liouville, 8 (1892), pp. 331-49.
%H A075195 E. Jablonski, Sur l'analyse combinatoire circulaire, Comptes-rendus de l'Académie des Sciences, April 11 1892, Paris.
%H A075195 E. Lucas, Sur les permutations circulaires avec répétition, Théorie des Nombres, Annexe VII, Gauthier-Villars, Paris, 1891. Mentions Moreau.
%H A075195 P. A. MacMahon, Application of a theory of permutations in circular procession to the theory of numbers, Proc. Lond. Math. Soc., 23 (1892), pp. 305-313. Mentions Jablonski, Lucas and Moreau.
%H A075195 Index entries for sequences related to necklaces
%F A075195 T(n,k) = (1/n)*Sum_{d | n} phi(d)*k^(n/d), where phi = Euler totient function A000010. - _Philippe Deléham_, Oct 08 2003
%F A075195 From _Petros Hadjicostas_, Feb 08 2021: (Start)
%F A075195 O.g.f. for column k >= 1: Sum_{n>=1} T(n,k)*x^n = -Sum_{d >= 1} (phi(d)/d) * log(1 - k*x^d).
%F A075195 Linear recurrence for row n >= 1: T(n,k) = Sum_{j=0..n} -binomial(j-n-1,j+1) * T(n,k-1-j) for k >= n + 2. (This recurrence is essentially due to _Robert A. Russell_, who contributed it in A321791.) (End)
%F A075195 From _Richard L. Ollerton_, May 07 2021: (Start)
%F A075195 T(n,k) = (1/n)*Sum_{i=1..n} k^gcd(n,i).
%F A075195 T(n,k) = (1/n)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).
%F A075195 T(n,k) = (1/n)*A185651(n,k) for n >= 1, k >= 1. (End)
%e A075195 The array T(n,k) for n >= 1, k >= 1 begins:
%e A075195 1, 2, 3, 4, 5, ...
%e A075195 1, 3, 6, 10, 15, ...
%e A075195 1, 4, 11, 24, 45, ...
%e A075195 1, 6, 24, 70, 165, ...
%e A075195 1, 8, 51, 208, 629, ...
%e A075195 From _Indranil Ghosh_, Mar 25 2017: (Start)
%e A075195 Triangle formed when the array is read by antidiagonals:
%e A075195 1
%e A075195 2, 1
%e A075195 3, 3, 1
%e A075195 4, 6, 4, 1
%e A075195 5, 10, 11, 6, 1
%e A075195 6, 15, 24, 24, 8, 1
%e A075195 7, 21, 45, 70, 51, 14, 1
%e A075195 8, 28, 76, 165, 208, 130, 20, 1
%e A075195 9, 36, 119, 336, 629, 700, 315, 36, 1
%e A075195 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1
%e A075195 ...
%e A075195 (End)
%t A075195 t[n_, k_] := (1/n)*Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 11}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Jan 20 2014, after _Philippe Deléham_ *)
%o A075195 (PARI) T(n, k) = (1/n) * sumdiv(n, d, eulerphi(d)*k^(n/d));
%o A075195 for(n=1, 15, for(k=1, n, print1(T(k, n - k + 1),", ");); print();) \\ _Indranil Ghosh_, Mar 25 2017
%o A075195 (Python)
%o A075195 from sympy.ntheory import totient, divisors
%o A075195 def T(n,k): return sum(totient(d)*k**(n//d) for d in divisors(n))//n
%o A075195 for n in range(1, 16):
%o A075195 print([T(k, n - k + 1) for k in range(1, n + 1)]) # _Indranil Ghosh_, Mar 25 2017
%Y A075195 Columns 1-10: A000012, A000031, A001867, A001868, A001869, A054625-A054629.
%Y A075195 Rows 1-10: A000027, A000217, A006527, A006528, A054620, A006565, A054621-A054624.
%Y A075195 Main Diagonal: A056665. A054630 and A054631 are the upper and lower triangles.
%Y A075195 Cf. A000010, A185651.
%K A075195 nonn,tabl
%O A075195 1,2
%A A075195 _Christian G. Bower_, Sep 07 2002
%E A075195 Additional references from _Philippe Deléham_, Oct 08 2003
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE