A081720 Triangle T(n,k) read by rows, giving number of bracelets (turnover necklaces) with n beads of k colors (n >= 1, 1 <= k <= n).
1, 1, 3, 1, 4, 10, 1, 6, 21, 55, 1, 8, 39, 136, 377, 1, 13, 92, 430, 1505, 4291, 1, 18, 198, 1300, 5895, 20646, 60028, 1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 1, 46, 1219, 15084, 110085, 563786, 2250311, 7472984, 21552969, 1, 78, 3210, 53764, 493131, 3037314
Offset: 1
Examples
1; (A000027) 1, 3; (A000217) 1, 4, 10; (A000292) 1, 6, 21, 55; (A002817) 1, 8, 39, 136, 377; (A060446) 1, 13, 92, 430, 1505, 4291; (A027670) 1, 18, 198, 1300, 5895, 20646, 60028; (A060532) 1, 30, 498, 4435, 25395, 107331, 365260, 1058058; (A060560) ... For example, when n=k=3, we have the following T(3,3)=10 bracelets of 3 beads using up to 3 colors: 000, 001, 002, 011, 012, 022, 111, 112, 122, and 222. (Note that 012 = 120 = 201 = 210 = 102 = 021.) _Petros Hadjicostas_, Nov 29 2017
References
- N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- Yi Hu, Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models, Master's Thesis, Duke Univ. (2021).
- Yi Hu and Patrick Charbonneau, Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices, arXiv:2106.08442 [cond-mat.stat-mech], 2021, cites the 4th column.
Crossrefs
Programs
-
Maple
A081720 := proc(n, k) local d, t1; t1 := 0; if n mod 2 = 0 then for d from 1 to n do if n mod d = 0 then t1 := t1+numtheory[phi](d)*k^(n/d); end if; end do: (t1+(n/2)*(1+k)*k^(n/2)) /(2*n) ; else for d from 1 to n do if n mod d = 0 then t1 := t1+numtheory[phi](d)*k^(n/d); end if; end do; (t1+n*k^((n+1)/2)) /(2*n) ; end if; end proc: seq(seq(A081720(n,k),k=1..n),n=1..10) ;
-
Mathematica
t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]); Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2012, after Maple, updated Nov 02 2017 *) Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n,k,Dihedral],{k,1,n}],{n,1,8}]//Grid (* Geoffrey Critzer, Oct 07 2012, after code by T. D. Noe in A027671 *)
Formula
See Maple code.
From Petros Hadjicostas, Nov 29 2017: (Start)
T(n,k) = ((1+k)*k^{n/2}/2 + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is even, and = (k^{(n+1)/2} + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is odd.
G.f. for column k: (1/2)*((k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)) provided we chop off the Taylor expansion starting at x^k (and ignore all the terms x^n with n
(End)
2*n*T(n,k) = A054618(n,k)+n*(1+k)^(n/2)/2 if n even, = A054618(n,k)+n*k^((n+1)/2) if n odd. - R. J. Mathar, Jan 23 2022
Extensions
Name edited by Petros Hadjicostas, Nov 29 2017
Comments