cp's OEIS Frontend

A308401 Number of bracelets (turnover necklaces) of length n that have no reflection symmetry and consist of 6 white beads and n-6 black beads.

%I A308401 #94 Feb 07 2021 00:51:54
%S A308401 3,6,16,30,56,91,150,224,336,477,672,912,1233,1617,2112,2700,3432,
%T A308401 4290,5340,6552,8008,9678,11648,13888,16503,19448,22848,26658,31008,
%U A308401 35853,41346,47424,54264,61803,70224,79464,89733,100947,113344,126840,141680,157780,175416,194480,215280,237708
%N A308401 Number of bracelets (turnover necklaces) of length n that have no reflection symmetry and consist of 6 white beads and n-6 black beads.
%C A308401 Bracelets that have no reflection symmetry are also known as chiral bracelets.
%C A308401 Here, for n >= 6, a(n) is also the number of dihedral compositions of n with 6 parts that have no reflection symmetry. Taking the MacMahon conjugates of these dihedral compositions, we see that a(n) is also the number of dihedral compositions of n into n-6 parts that have no reflection symmetry.
%C A308401 A cyclic composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation. Such compositions were first studied extensively by Sommerville (1909).
%C A308401 A dihedral composition b_1 + b_2 + ... + b_k of n into k parts is an equivalent class of (linear) compositions of n into k parts (placed on a circle) such that two such (linear) compositions are equivalent iff one can be obtained from the other by a rotation or a reversal of order. Such compositions were studied, for example, by Knopfmacher and Robbins (2013).
%C A308401 Given a bracelet of length n with k white beads and n-k black beads, we may get the corresponding dihedral composition using MacMahon's correspondence: start with a white bead and count that bead and the black beads that follow (in one direction), and call that b_1; then start with the next white bead and count that one and the black beads that follow, and call that b_2; repeat this process until you reach the k-th white bead and count that one and the black beads that follow, and call that b_k. The corresponding dihedral composition is b_1 + b_2 + ... + b_k.
%C A308401 If in the previous paragraph (given a bracelet of length n with k white beads and n-k black beads), we replace the white beads with black beads and the black beads with white beads, we get a dihedral composition of n into n-k parts: c_1 + c_2 + ... + c_{n-k}. These two dihedral compositions (which correspond to the same bracelet) are called "conjugate" compositions. See p. 273 in Sommerville (1909) for an explanation of "conjugate" compositions in the context of cyclic compositions.
%C A308401 Symmetric cyclic compositions of a positive integer n were first studied by Sommerville (1909, pp. 301-304). It can be proved that the study of necklaces with reflection symmetry using beads of two colors is equivalent to the study of symmetric cyclic compositions of a positive integer. Clearly all the necklaces with reflection symmetry are all the bracelets (turnover necklaces) with reflection symmetry. See also the comments for sequences A119963, A292200, and A295925.
%H A308401 Colin Barker, <a href="/A308401/b308401.txt">Table of n, a(n) for n = 9..1000</a>
%H A308401 Hansraj Gupta, <a href="https://web.archive.org/web/20200806162943/https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a66_964.pdf">Enumeration of incongruent cyclic k-gons</a>, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
%H A308401 Petros Hadjicostas, <a href="/A308401/a308401.pdf">The aperiodic version of Herbert Kociemba's formula for bracelets with no reflection symmetry</a>, 2019.
%H A308401 Arnold Knopfmacher and Neville Robbins, <a href="https://www.researchgate.net/publication/260006088_Some_Properties_of_Dihedral_Compositions">Some properties of dihedral compositions</a>, Util. Math. 92 (2013), 207-220.
%H A308401 Richard H. Reis, <a href="https://web.archive.org/web/20200803213425/https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a66_1000.pdf">A formula for C(T) in Gupta's paper</a>, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 1000-1001.
%H A308401 Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A308401 Vladimir S. Shevelev, <a href="http://www.math.bgu.ac.il/~shevelev/Shevelev_Neclaces.pdf">Necklaces and convex k-gons</a>, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
%H A308401 Vladimir S. Shevelev, <a href="https://web.archive.org/web/20200722171019/http://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/2000c4e8_629.pdf">Necklaces and convex k-gons</a>, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
%H A308401 Duncan M. Y. Sommerville, <a href="https://doi.org/10.1112/plms/s2-7.1.263">On certain periodic properties of cyclic compositions of numbers</a>, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
%H A308401 <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-3,-1,1,4,-3,-3,4,1,-1,-3,1,2,-1).
%F A308401 G.f.: (x^k/2) * (-(1 + x)/(1 - x^2)^floor((k/2) + 1) + (1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m)) with k = 6. (This formula is due to Herbert Kociemba.)
%F A308401 a(n) = A005513(n) - A058187(n-6) = A005513(n) - binomial(floor(n/2), 3) for n >= 6.
%F A308401 a(n) =  -(1/2)*binomial(floor(n/2), 3) + (1/12)* Sum_{d|gcd(n, 6)} phi(d)*binomial((n/d) - 1, (6/d) - 1) for n >= 6. (This is a modification of formulas found in Gupta (1979) and Shevelev (2004).)
%F A308401 From _Colin Barker_, May 26 2019: (Start)
%F A308401 G.f.: x^9*(3 + x^2 + x^3 + x^4) / ((1 - x)^6*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)^2).
%F A308401 a(n) = 2*a(n-1) + a(n-2) - 3*a(n-3) - a(n-4) + a(n-5) + 4*a(n-6) - 3*a(n-7) - 3*a(n-8) + 4*a(n-9) + a(n-10) - a(n-11) - 3*a(n-12) + a(n-13) + 2*a(n-14) - a(n-15) for n > 23. (End)
%e A308401 Using Frank Ruskey's website (listed above) to generate bracelets of fixed content (6, 3) with string length n = 9 and alphabet size 2, we get the following A005513(n = 9) = 7 bracelets: (1) WWWWWWBBB, (2) WWWWWBWBB, (3) WWWWBWWBB, (4) WWWWBWBWB, (5) WWWBWWWBB, (6) WWWBWWBWB, and (7) WWBWWBWWB. From these, bracelets 1, 4, 5, and 7 have reflection symmetry, while bracelets 2, 3 and 6 have no reflection symmetry (and thus, a(9) = 3).
%e A308401 Starting with a black bead, we count that bead and how many white beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence to get the following dihedral compositions of n = 9 into 3 parts: (1) 1 + 7 + 1, (2) 1 + 2 + 6, (3) 1 + 3 + 5, (4) 2 + 5 + 2, (5) 4 + 1 + 4, (6) 2 + 3 + 4, and (7) 3 + 3 + 3. Again, dihedral compositions 1, 4, 5, and 7 are symmetric (have reflection symmetry), while dihedral compositions 2, 3, and 6 are not symmetric (and thus, a(9) = 3).
%e A308401 We may also start with a white bead and count that bead and how many black beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence again to get the following (conjugate) dihedral compositions of n = 9 into 6 parts: (1) 1 + 1 + 1 + 1 + 1 + 4, (2) 1 + 1 + 1 + 1 + 2 + 3, (3) 1 + 1 + 1 + 2 + 1 + 3, (4) 1 + 1 + 1 + 2 + 2 + 2, (5) 1 + 1 + 2 + 1 + 1 + 3, (6) 1 + 1 + 2 + 1 + 2 + 2, and (7) 1 + 2 + 1 + 2 + 1 + 2. Again, dihedral compositions 1, 4, 5, and 7 have reflection symmetries, while dihedral compositions 2, 3, and 6 do not have reflection symmetries (and thus, a(9) = 3). For example, dihedral composition 1 is symmetric because we can draw an axis of symmetry through one of the 1s and 4. In addition, dihedral composition 5 is symmetric because we may draw an axis of symmetry through the numbers 2 and 3.
%o A308401 (PARI) a(n) = (1/12)* (sumdiv(gcd(n, 6), d,  eulerphi(d)*binomial((n/d) - 1, (6/d) - 1))) - (1/2)*binomial(floor(n/2), 3); \\ _Michel Marcus_, May 28 2019
%o A308401 (PARI) Vec(x^9*(3 + x^2 + x^3 + x^4) / ((1 - x)^6*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)^2) + O(x^50)) \\ _Colin Barker_, Jun 02 2019
%Y A308401 Cf. A005513, A008804, A032246, A032247, A032248, A032249, A058187, A119963, A292200, A295925. Column k = 6 of A180472.
%K A308401 nonn,easy
%O A308401 9,1
%A A308401 _Petros Hadjicostas_, May 24 2019