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