login
A075195
Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.
32
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, 28, 76, 165, 208, 130, 20, 1, 9, 36, 119, 336, 629, 700, 315, 36, 1, 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1, 11, 55, 249, 1044, 3367, 7826, 11165, 8230, 2195, 108, 1
OFFSET
1,2
COMMENTS
From Richard L. Ollerton, May 07 2021: (Start)
Here, as in A000031, turning over is not allowed.
(1/n) * Dirichlet convolution of phi(n) and k^n. (End)
REFERENCES
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 86 (2.2.23).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 496.
Louis Comtet, Analyse combinatoire, Tome 2, p. 104 #17, P.U.F., 1970.
LINKS
E. Jablonski, Théorie des permutations et des arrangements complets, Journal de Liouville, 8 (1892), pp. 331-49.
E. Jablonski, Sur l'analyse combinatoire circulaire, Comptes-rendus de l'Académie des Sciences, April 11 1892, Paris.
E. Lucas, Sur les permutations circulaires avec répétition, Théorie des Nombres, Annexe VII, Gauthier-Villars, Paris, 1891. Mentions Moreau.
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.
FORMULA
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
From Petros Hadjicostas, Feb 08 2021: (Start)
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).
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)
From Richard L. Ollerton, May 07 2021: (Start)
T(n,k) = (1/n)*Sum_{i=1..n} k^gcd(n,i).
T(n,k) = (1/n)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*A185651(n,k) for n >= 1, k >= 1. (End)
EXAMPLE
The array T(n,k) for n >= 1, k >= 1 begins:
1, 2, 3, 4, 5, ...
1, 3, 6, 10, 15, ...
1, 4, 11, 24, 45, ...
1, 6, 24, 70, 165, ...
1, 8, 51, 208, 629, ...
From Indranil Ghosh, Mar 25 2017: (Start)
Triangle formed when the array is read by antidiagonals:
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, 28, 76, 165, 208, 130, 20, 1
9, 36, 119, 336, 629, 700, 315, 36, 1
10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1
...
(End)
MATHEMATICA
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 *)
PROG
(PARI) T(n, k) = (1/n) * sumdiv(n, d, eulerphi(d)*k^(n/d));
for(n=1, 15, for(k=1, n, print1(T(k, n - k + 1), ", "); ); print(); ) \\ Indranil Ghosh, Mar 25 2017
(Python)
from sympy.ntheory import totient, divisors
def T(n, k): return sum(totient(d)*k**(n//d) for d in divisors(n))//n
for n in range(1, 16):
print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Mar 25 2017
CROSSREFS
Main Diagonal: A056665. A054630 and A054631 are the upper and lower triangles.
Sequence in context: A074909 A135278 A034356 * A293311 A126885 A239986
KEYWORD
nonn,tabl
AUTHOR
Christian G. Bower, Sep 07 2002
EXTENSIONS
Additional references from Philippe Deléham, Oct 08 2003
STATUS
approved