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
A295925 Number of bilaterally asymmetric 8-hoops with n symbols.
6, 336, 3795, 23520, 102795, 355656, 1039626, 2674440, 6223140, 13354440, 26807781, 50885016, 92095185, 159981360, 268161060, 435614256, 688255506, 1060829280, 1599170055, 2362871280, 3428409831, 4892775096, 6877654350
Offset: 2
Comments
This is a corrected version of the entries in sequence A210769, which is copied from the third row of Table 2 (p. 381) in Williamson (1972). Apparently, in that row, there are probable typographical errors for the values of a(4) and a(7). The formula for a(n) can be obtained by letting z_1=z_2=...=z_8=n in equation (24) on p. 377 in Williamson (1972). In any case, to be certain, we provide a sketch of an independent derivation of the formula.
Bilaterally symmetric bracelets are also known as circular palindromes. This kind of necklaces was first studied by Sommerville (1909) in the context of circular compositions.
Consider sequence A081720, which contains the numbers T(n,k) that are the number of bracelets (turn over necklaces) with n beads each of which is colored with one of k colors. The g.f. for column k of that triangle is (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)). The part of the g.f. that is the number of bilaterally symmetric bracelets with n beads of k colors is (k*x+k*(k+1)*x^2/2)/(1-k*x^2). Thus, for fixed k (= number of colors for sequence A081720), the g.f. of the number of bilaterally asymmetric bracelets with n beads of k colors is the difference between the two g.f.'s, that is, (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)). The coefficient of x^8 in the Taylor expansion w.r.t. x (around x=0) for the latter g.f. gives the number of bilaterally asymmetric 8-hoops obtained using (up to) k symbols. Taking the 8th derivative w.r.t. x of the last g.f., evaluating at x=0, dividing by 8!, and replacing k with n, we get the formulae given below.
Examples
From the A060560(2) = 30 8-hoops (i.e., from the total number of ways of coloring the vertices of an octagon using up to n=2 colors, allowing for rotations and reflections), there are A019583(2+1) = 24 that are circular palindromes (i.e., bilaterally symmetric bracelets). Hence, there are 30-24=6 bilaterally asymmetric 8-hoops using up to 2 colors. They are the following: 01001111, 01000111, 01000011, 00101011, 00110111 and 11001000. (To view these 6 asymmetric bracelets, the 0's and 1's must be placed on the vertices of a regular octagon inscribed in a circle as it is done in Fig. 4 on p. 379 in Williamson (1972), where 0 is replaced by a and 1 by b.)
Links
- D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
- S. G. Williamson, The combinatorial analysis of patterns and the principle of inclusion-exclusion, Discrete Math. 1 (1972), 357-388.
- Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).
Crossrefs
Programs
-
Mathematica
Drop[#, 2] &@ CoefficientList[Series[3 (7 x^4 + 82 x^3 + 237 x^2 + 92 x + 2) (x + 1) x^2/(1 - x)^9, {x, 0, 24}], x] (* Michael De Vlieger, Dec 02 2017 *)
Formula
a(n) = (1/16)*(n^3-n^2-2)*(n^2+n+2)*(n+1)*(n-1)*n = (n^8-4*n^5-3*n^4+2*n^2+4*n)/16.
a(n) = A060560(n) - A019583(n+1) = (A054622(n) - A019583(n+1))/2. (Notice that the offsets of the sequences in these formulae are not necessarily the same as the offset of the current sequence.)
G.f.: 3*(7*x^4 + 82*x^3 + 237*x^2 + 92*x + 2)*(x + 1)*x^2/(1-x)^9.
Recurrence: (1-Delta)^9 a(n) = 0, where Delta^m a(n) = a(n-m). Hence, a(n) = 9*a(n-1)-36*a(n-2)+84*a(n-3)-126*a(n-4)+126*a(n-5)-84*a(n-6)+36*a(n-7)-9*a(n-8)+a(n-9).
E.g.f.: exp(x)*x^2*(48 + 848*x + 1658*x^2 + 1046*x^3 + 266*x^4 + 28*x^5 + x^6)/16. - Stefano Spezia, Feb 18 2024
A210766 Number of 8-hoops with n symbols and no a-rooted trees.
1, 13, 141, 1204, 7570, 36021, 136948, 436696, 1212399, 3013165, 6843991, 14431308, 28591576, 53726869, 96473910, 166535536, 277726093, 449264781, 707353489, 1087078180
Offset: 1
Links
- S. G. Williamson, The combinatorial analysis of patterns and the principle of inclusion-exclusion, Discrete Math. 1 (1972), no. 4, 357--388. MR0299493 (45 #8541).
- Index entries for linear recurrences with constant coefficients, signature (9, -36, 84, -126, 126, -84, 36, -9, 1).
Programs
-
Maple
A210766 := proc(n) (n^8-8*n^7+36*n^6-92*n^5+155*n^4-148*n^3 +88*n^2-16*n)/16 ; end proc: # R. J. Mathar, Mar 27 2012
Formula
G.f.: x*(1+x)*(1+3*x+57*x^2+262*x^3+582*x^4+321*x^5+34*x^6)/(1-x)^9. [Colin Barker, Apr 17 2012]
A210768 Number of bilaterally asymmetric 8-hoops with n symbols and no a-rooted trees.
1, 3, 918, 6669, 33665, 131616, 425866, 1192178, 2977857
Offset: 2
Keywords
Comments
It appears that table 2 of the Williamson article contains typographical errors and the sequence was intended to read as in A210699.
Links
- Williamson, S. G. The combinatorial analysis of patterns and the principle of inclusion-exclusion. Discrete Math. 1 (1972), no. 4, 357--388. MR0299493 (45 #8541)
Comments