A075195 - OEIS

%I #87 May 10 2021 15:34:53

%S 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 28,76,165,208,130,20,1,9,36,119,336,629,700,315,36,1,10,45,176,616,

%U 1560,2635,2344,834,60,1,11,55,249,1044,3367,7826,11165,8230,2195,108,1

%N Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.

%C From _Richard L. Ollerton_, May 07 2021: (Start)

%C Here, as in A000031, turning over is not allowed.

%C (1/n) * Dirichlet convolution of phi(n) and k^n. (End)

%D F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 86 (2.2.23).

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 496.

%D Louis Comtet, Analyse combinatoire, Tome 2, p. 104 #17, P.U.F., 1970.

%H Andrew Howroyd, <a href="/A075195/b075195.txt">Table of n, a(n) for n = 1..1275</a>

%H E. Jablonski, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1892_4_8_A9_0.pdf">Théorie des permutations et des arrangements complets</a>, Journal de Liouville, 8 (1892), pp. 331-49.

%H E. Jablonski, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k3070h/f904">Sur l'analyse combinatoire circulaire</a>, Comptes-rendus de l'Académie des Sciences, April 11 1892, Paris.

%H E. Lucas, <a href="https://archive.org/details/thoriedesnombre00lucagoog/page/n505">Sur les permutations circulaires avec répétition</a>, Théorie des Nombres, Annexe VII, Gauthier-Villars, Paris, 1891. Mentions Moreau.

%H P. A. MacMahon, <a href="https://archive.org/details/proceedingslond25socigoog/page/n314">Application of a theory of permutations in circular procession to the theory of numbers</a>, Proc. Lond. Math. Soc., 23 (1892), pp. 305-313. Mentions Jablonski, Lucas and Moreau.

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F 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 From _Petros Hadjicostas_, Feb 08 2021: (Start)

%F 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 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 From _Richard L. Ollerton_, May 07 2021: (Start)

%F T(n,k) = (1/n)*Sum_{i=1..n} k^gcd(n,i).

%F T(n,k) = (1/n)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).

%F T(n,k) = (1/n)*A185651(n,k) for n >= 1, k >= 1. (End)

%e The array T(n,k) for n >= 1, k >= 1 begins:

%e   1, 2,  3,   4,   5, ...

%e   1, 3,  6,  10,  15, ...

%e   1, 4, 11,  24,  45, ...

%e   1, 6, 24,  70, 165, ...

%e   1, 8, 51, 208, 629, ...

%e From _Indranil Ghosh_, Mar 25 2017: (Start)

%e Triangle formed when the array is read by antidiagonals:

%e     1

%e     2,  1

%e     3,  3,   1

%e     4,  6,   4,   1

%e     5, 10,  11,   6,    1

%e     6, 15,  24,  24,    8,    1

%e     7, 21,  45,  70,   51,   14,    1

%e     8, 28,  76, 165,  208,  130,   20,   1

%e     9, 36, 119, 336,  629,  700,  315,  36,  1

%e    10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1

%e    ...

%e (End)

%t 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 (PARI) T(n, k) = (1/n) * sumdiv(n, d, eulerphi(d)*k^(n/d));

%o for(n=1, 15, for(k=1, n, print1(T(k, n - k + 1),", ");); print();) \\ _Indranil Ghosh_, Mar 25 2017

%o (Python)

%o from sympy.ntheory import totient, divisors

%o def T(n,k): return sum(totient(d)*k**(n//d) for d in divisors(n))//n

%o for n in range(1, 16):

%o     print([T(k, n - k + 1) for k in range(1, n + 1)]) # _Indranil Ghosh_, Mar 25 2017

%Y Columns 1-10: A000012, A000031, A001867, A001868, A001869, A054625-A054629.

%Y Rows 1-10: A000027, A000217, A006527, A006528, A054620, A006565, A054621-A054624.

%Y Main Diagonal: A056665. A054630 and A054631 are the upper and lower triangles.

%Y Cf. A000010, A185651.

%K nonn,tabl

%O 1,2

%A _Christian G. Bower_, Sep 07 2002

%E Additional references from _Philippe Deléham_, Oct 08 2003