|
%I M3801 #136 Oct 17 2022 01:46:00
%S 1,1,5,10,29,57,126,232,440,750,1282,2052,3260,4950,7440,10824,15581,
%T 21879,30415,41470,56021,74503,98254,127920,165288,211276,268228,
%U 337416,421856,523260,645456,790704,963793,1167645,1408185
%N Number of n-bead bracelets (turnover necklaces) with 8 red beads and n-8 black beads.
%C From _Vladimir Shevelev_, Apr 23 2011: (Start)
%C Also number of non-equivalent necklaces of 8 beads each of them painted by one of n colors.
%C The sequence solves the so-called Reis problem about convex k-gons in case k=8 (see our comment at A032279).
%C (End)
%C From _Petros Hadjicostas_, Jul 14 2018: (Start)
%C Let (c(n): n >= 1) be a sequence of nonnegative integers and let C(x) = Sum_{n>=1} c(n)*x^n be its g.f. Let k be a positive integer. Let a_k = (a_k(n): n >= 1) be the output sequence of the DIK[k] transform of sequence (c(n): n >= 1), and let A_k(x) = Sum_{n>=1} a_k(n)*x^n be its g.f. See Bower's web link below. It can be proved that, when k is even, A_k(x) = ((1/k)*Sum_{d|k} phi(d)*C(x^d)^(k/d) + (1/2)*C(x^2)^((k/2)-1)*(C(x)^2 + C(x^2)))/2.
%C For this sequence, k=8, c(n) = 1 for all n >= 1, and C(x) = x/(1-x). Thus, a(n) = a_8(n) for all n >= 1. Since a_k(n) = 0 for 1 <= n <= k-1, the offset of this sequence is n = k = 8. Applying the formula for the g.f. of DIK[8] of (c(n): n >= 1) with C(x) = x/(1-x) and k=8, we get _Herbert Kociemba_'s formula below.
%C Here, a(n) is defined to be the number of n-bead bracelets of two colors with 8 red beads and n-8 black beads. But it is also the number of dihedral compositions of n with 8 parts. (This statement is equivalent to _Vladimir Shevelev_'s statement above that a(n) is the "number of non-equivalent necklaces of 8 beads each of them painted by one of n colors." By "necklaces", he means "turnover necklaces". See the second paragraph of Section 2 in his 2004 paper in the Indian Journal of Pure and Applied Mathematics.)
%C Two cyclic compositions of n (with k = 8 parts) belong to the same equivalence class corresponding to a dihedral composition of n if and only if one can be obtained from the other by a rotation or reversal of order. (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
%H Andrew Howroyd, <a href="/A005514/b005514.txt">Table of n, a(n) for n = 8..1000</a>
%H Christian G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H S. J. Cyvin, B. N. Cyvin, J. Brunvoll, I. Gutman, Chen Rong-si, S. El-Basil, and Zhang Fuji, <a href="http://zfn.mpdl.mpg.de/data/Reihe_A/52/ZNA-1997-52a-0867.pdf">Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem</a>, Z. Naturforsch., 52a (1997), 867-873.
%H 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 W. D. Hoskins and Anne Penfold Street, <a href="http://dx.doi.org/10.1017/S1446788700017547">Twills on a given number of harnesses</a>, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 1-15.
%H W. D. Hoskins and A. P. Street, <a href="/A005513/a005513_1.pdf">Twills on a given number of harnesses</a>, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)
%H 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 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Vladimir 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 Vladimir Shevelev, <a href="https://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 Vladimir Shevelev, <a href="http://arxiv.org/abs/1104.4051">Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma)</a>, arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
%H A. P. Street, <a href="/A005513/a005513.pdf">Letter to N. J. A. Sloane, N.D.</a>
%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F S. J. Cyvin et al. (1997) give a g.f. (See equation (18) on p. 870 of their paper. Their g.f. is the same as the one given by V. Jovovic below except for the extra x^8.) - _Petros Hadjicostas_, Jul 14 2018)
%F G.f.: (x^8/16)*(1/(1 - x)^8 + 4/(1 - x^8) + 5/(1 - x^2)^4 + 2/(1 - x^4)^2 + 4/(1 - x)^2/(1 - x^2)^3) = x^8*(2*x^10 - 3*x^9 + 7*x^8 - 6*x^7 + 7*x^6 - 2*x^5 + 2*x^4 - 2*x^3 + 5*x^2 - 3*x + 1)/(1 - x)^8/(1 + x)^4/(1 + x^2)^2/(1 + x^4). - _Vladeta Jovovic_, Jul 17 2002
%F From _Vladimir Shevelev_, Apr 23 2011: (Start)
%F Let s(n,k,d)=1, if n == k (mod d), and 0 otherwise. Then
%F a(n) = ((n+4)/32)*s(n,0,8) + ((n-4)/32)*s(n,4,8) + (48*C(n-1,7) + (n+1)*(n-2)*(n-4)*(n-6))/768, if n is even >= 8; a(n) = (48*C(n-1,7) + (n-1)*(n-3)*(n-5)*(n-7))/768, if n odd >= 8.
%F (End)
%F G.f.: k=8, x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^floor((k+2)/2))/2. - _Herbert Kociemba_, Nov 05 2016 [edited by _Petros Hadjicostas_, Jul 18 2018]
%F From _Petros Hadjicostas_, Jul 14 2018: (Start)
%F a(n) = (A032193(n) + A119963(n, 8))/2 = (A032193(n) + C(floor(n/2), 4))/2 for n >= 8.
%F The sequence (a(n): n >= 8) is the output sequence of Bower's "DIK[ 8 ]" (bracelet, indistinct, unlabeled, 8 parts) transform of 1, 1, 1, 1, ...
%F (End)
%e From _Petros Hadjicostas_, Jul 14 2018: (Start)
%e Every n-bead bracelet of two colors such that 8 beads are red and n-8 are black can be transformed into a dihedral composition of n with 8 parts in the following way. Start with one R bead and go in one direction (say clockwise) until you reach the next R bead. Continue this process until you come back to the original R bead.
%e Let b_i be the number of beads from R bead i until you reach the last B bead before R bead i+1 (or R bead 1). Here, b_i = 1 iff there are no B beads between R bead i and R bead i+1 (or R bead 8 and R bead 1). Then b_1 + b_2 + ... + b_8 = n, and we get a dihedral composition of n. (Of course, b_2 + b_3 + ... + b_8 + b_1 and b_8 + b_7 + ... + b_1 belong to the same equivalence class of the dihedral composition b_1 + ... + b_8.)
%e For example, a(10) = 5, and we have the following bracelets with 8 R beads and 2 B beads. Next to the bracelets we list the corresponding dihedral compositions of n with k=8 parts (they must be viewed on a circle):
%e RRRRRRRRBB <-> 1+1+1+1+1+1+1+3
%e RRRRRRRBRB <-> 1+1+1+1+1+1+2+2
%e RRRRRRBRRB <-> 1+1+1+1+1+2+1+2
%e RRRRRBRRRB <-> 1+1+1+1+2+1+1+2
%e RRRRBRRRRB <-> 1+1+1+2+1+1+1+2
%e (End)
%t k = 8; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* _Robert A. Russell_, Sep 27 2004 *)
%t k=8;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* _Herbert Kociemba_, Nov 04 2016 *)
%Y Column k=8 of A052307.
%Y Cf. A008805, A032193, A032279, A032280, A032281, A032282, A119963, A292906.
%K nonn,easy,nice
%O 8,3
%A _N. J. A. Sloane_
%E Sequence extended and description corrected by _Christian G. Bower_
%E Name edited by _Petros Hadjicostas_, Jul 20 2018
|
