cp's OEIS Frontend

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).

%I A081720 #74 Feb 05 2024 14:20:49
%S A081720 1,1,3,1,4,10,1,6,21,55,1,8,39,136,377,1,13,92,430,1505,4291,1,18,198,
%T A081720 1300,5895,20646,60028,1,30,498,4435,25395,107331,365260,1058058,1,46,
%U A081720 1219,15084,110085,563786,2250311,7472984,21552969,1,78,3210,53764,493131,3037314
%N 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).
%C A081720 From _Petros Hadjicostas_, Nov 29 2017: (Start)
%C A081720 The formula given below is clear from the programs given in the Maple and Mathematica sections, while the g.f. for column k can be obtained using standard techniques.
%C A081720 If we differentiate the column k g.f. m times, then we can get a formula for row m. (For this sequence, we only need to use this row m formula for 1 <= k <= m, but it is valid even for k>m.) For example, to get the formula for row 8, we have T(n=8,k) = d^8/dx^8 (column k g.f.)/8! evaluated at x=0. Here, "d^8/dx^8" means "8th derivative w.r.t. x" of the column k g.f. Doing so, we get T(n=8, k) = (k^6 - k^5 + k^4 + 3*k^3 + 2*k^2 - 2*k + 4)*(k + 1)*k/16, which is the formula given for sequence A060560. (Here, we use this formula only for 1 <= k <= 8.)
%C A081720 (End)
%D A081720 N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
%H A081720 Andrew Howroyd, <a href="/A081720/b081720.txt">Table of n, a(n) for n = 1..1275</a>
%H A081720 Yi Hu, <a href="https://hdl.handle.net/10161/23828">Numerical Transfer Matrix Method of Next-nearest-neighbor Ising Models</a>, Master's Thesis, Duke Univ. (2021).
%H A081720 Yi Hu and Patrick Charbonneau, <a href="https://arxiv.org/abs/2106.08442">Numerical transfer matrix study of frustrated next-nearest-neighbor Ising models on square lattices</a>, arXiv:2106.08442 [cond-mat.stat-mech], 2021, cites the 4th column.
%F A081720 See Maple code.
%F A081720 From _Petros Hadjicostas_, Nov 29 2017: (Start)
%F A081720 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.
%F A081720 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<k).
%F A081720 (End)
%F A081720 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
%e A081720 1;                                                (A000027)
%e A081720 1,  3;                                            (A000217)
%e A081720 1,  4,  10;                                       (A000292)
%e A081720 1,  6,  21,   55;                                 (A002817)
%e A081720 1,  8,  39,  136,   377;                          (A060446)
%e A081720 1, 13,  92,  430,  1505,   4291;                  (A027670)
%e A081720 1, 18, 198, 1300,  5895,  20646,  60028;          (A060532)
%e A081720 1, 30, 498, 4435, 25395, 107331, 365260, 1058058; (A060560)
%e A081720 ...
%e A081720 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
%p A081720 A081720 := proc(n, k)
%p A081720     local d, t1;
%p A081720     t1 := 0;
%p A081720     if n mod 2 = 0 then
%p A081720         for d from 1 to n do
%p A081720             if n mod d = 0 then
%p A081720                 t1 := t1+numtheory[phi](d)*k^(n/d);
%p A081720             end if;
%p A081720         end do:
%p A081720         (t1+(n/2)*(1+k)*k^(n/2)) /(2*n) ;
%p A081720     else
%p A081720         for d from 1 to n do
%p A081720             if n mod d = 0 then
%p A081720                 t1 := t1+numtheory[phi](d)*k^(n/d);
%p A081720             end if;
%p A081720         end do;
%p A081720         (t1+n*k^((n+1)/2)) /(2*n) ;
%p A081720     end if;
%p A081720 end proc:
%p A081720 seq(seq(A081720(n,k),k=1..n),n=1..10) ;
%t A081720 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 *)
%t A081720 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 *)
%Y A081720 Cf. A321791 (extension to n >= 0, k >= 0).
%Y A081720 Cf. A081721 (diagonal), A081722 (row sums), column sequences k=2..6: A000029, A027671, A032275, A032276, A056341.
%K A081720 nonn,tabl
%O A081720 1,3
%A A081720 _N. J. A. Sloane_, based on information supplied by _Gary W. Adamson_, Apr 05 2003
%E A081720 Name edited by _Petros Hadjicostas_, Nov 29 2017