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

Author

Petros Hadjicostas, Nov 30 2017

Keywords

• nonn
• easy

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

Cf. A019583, A054622, A060560, A081720, A119963, A210699, A210766, A210768, A295925, A292200.

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