A075195 Jablonski table T(n,k) read by antidiagonals: T(n,k) = number of necklaces with n beads of k colors.
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
Examples
The array T(n,k) for n >= 1, k >= 1 begins: 1, 2, 3, 4, 5, 6, 7, ... 1, 3, 6, 10, 15, 21, 28, ... 1, 4, 11, 24, 45, 76, 119, ... 1, 6, 24, 70, 165, 336, 616, ... 1, 8, 51, 208, 629, 1560, 3367, ... 1, 14, 130, 700, 2635, 7826, 19684, ... 1, 20, 315, 2344, 11165, 39996, 117655, ... 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)
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
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- 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.
- Index entries for sequences related to necklaces
Crossrefs
Programs
-
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 *) -
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
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_{j >= 1} (phi(j)/j) * log(1 - k*x^j).
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)
Product_{n>=1} 1/(1 - x^n)^T(n,k) = Product_{n>=1} 1/(1 - k*x^n). - Seiichi Manyama, Apr 12 2025
Extensions
Additional references from Philippe Deléham, Oct 08 2003
Comments