|
%I #192 Oct 17 2022 01:54:33
%S 1,1,3,5,10,16,26,38,57,79,111,147,196,252,324,406,507,621,759,913,
%T 1096,1298,1534,1794,2093,2421,2793,3199,3656,4152,4706,5304,5967,
%U 6681,7467,8311,9234,10222,11298,12446,13691,15015,16445
%N Number of bracelets (turnover necklaces) of n beads of 2 colors, 5 of them black.
%C From _Vladimir Shevelev_, Apr 23 2011: (Start)
%C Also number of non-equivalent necklaces of 5 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=5. The full solution was given by H. Gupta (1979); I gave a short proof of Gupta's result and showed an equivalence of this problem and every one of the following problems: enumerating the bracelets of n beads of 2 colors, k of them black, and enumerating the necklaces of k beads each of them painted by one of n colors.
%C a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order n with five 1's in every row. (End)
%C a(n+5) is the number of symmetry-allowed, linearly-independent terms at n-th order in the series expansion of the T_1 X h vibronic perturbation matrix, H(Q) (cf. Dunn & Bates). - _Bradley Klee_, Jul 20 2015
%C From _Petros Hadjicostas_, Jul 17 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 _Christian G. Bower_'s web link below. It can be proved that, when k is odd, A_k(x) = ((1/k)*Sum_{d|k} phi(d)*C(x^d)^(k/d) + C(x^2)^((k-1)/2)*C(x))/2.
%C For this sequence, k = 5, c(n) = 1 for all n >= 1, and C(x) = x/(1-x). Thus, a(n) = a_5(n) for all n >= 1. Since a_k(n) = 0 for 1 <= n <= k-1, the offset of this sequence is n = k = 5. Applying the formula for the g.f. of DIK[5] of (c(n): n >= 1) with C(x) = x/(1-x) and k = 5, we get A(x) = A_5(x) = x^5*((1/5)*Sum_{d|5} phi(d)*(1-x^d)^(-5/d) + (1+x)/(1-x^2)^3)/2, which obviously equals the g.f. in the formula section below.
%C The g.f. is also a special case of _Herbert Kociemba_'s formula that is valid for both even and odd k: A_k(x) = x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^Floor[(k+2)/2])/2.
%C Here, a(n) is defined to be the number of n-bead bracelets of two colors with 5 black beads and n-5 white beads. But it is also the number of dihedral compositions of n with 5 positive parts. (This statement is equivalent to _Vladimir Shevelev_'s statement above that a(n) is the "number of non-equivalent necklaces of 5 beads each of them painted by one of n colors." By "necklaces" he means "turnover necklaces". See paragraph (2) of Section 2 in his 2004 paper in the Indian Journal of Pure and Applied Mathematics.)
%C Two cyclic compositions of n (with k = 5 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. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
%H Vincenzo Librandi, <a href="/A032279/b032279.txt">Table of n, a(n) for n = 5..1000</a>
%H Nesrine Benyahia-Tani, Zahra Yahi, and Sadek Bouroubi <a href="http://ftp.math.uni-rostock.de/pub/romako/heft68/bouroubi68.html">Ordered and non-ordered non-congruent convex quadrilaterals inscribed in a regular n-gon.</a> Rostocker Math. Kolloq. 68, 71-79 (2013), Theorem 1.
%H N. Benyahia Tani, Z. Yahi, and S. Bouroubi, <a href="https://liforce.usthb.dz/sites/default/files/2020-11/article1.pdf">Ordered and non-ordered non-isometric convex quadrilaterals inscribed in a regular n-gon</a>, Bulletin du Laboratoire Liforce, 01 (2014) 1-9.
%H C. 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 J. L. Dunn and C. A. Bates, <a href="http://dx.doi.org/10.1103/PhysRevB.52.5996">Analysis of the T1u(x)hg system as a model for C60 molecules</a>, Phys. Rev. B 52, 5996, 15 August 1995.
%H H. 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., Vol. 10, No. 8 (1979), 964-999.
%H E. Kirkman, J. Kuzmanovich, and J. J. Zhang, <a href="http://arxiv.org/abs/1305.3973">Invariants of (-1)-Skew Polynomial Rings under Permutation Representations</a>, arXiv preprint arXiv:1305.3973, 2013. See Example 5.5.
%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., Vol. 10 , No. 8 (1979), 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="http://www.math.bgu.ac.il/~shevelev/Shevelev_Neclaces.pdf">Necklaces and convex k-gons</a>, Indian J. Pure and Appl. Math., Vol. 35, No. 5 (2004), 629-638.
%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., Vol. 35, No. 5 (2004), 629-638.
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0710.1370">A problem of enumeration of two-color bracelets with several variations</a>, arXiv:0710.1370 [math.CO], 2007-2011.
%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 href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F "DIK[ 5 ]" (necklace, indistinct, unlabeled, 5 parts) transform of 1, 1, 1, 1, ...
%F G.f.: x^5*(1-x+2*x^3-x^5+x^6)/((1-x)^2*(1-x^2)^2*(1-x^5)). - corrected for offset 5 by _Robert Israel_, Jul 22 2015
%F From _Vladimir Shevelev_, Apr 23 2011: (Start)
%F Put s(n,k,d)=1, if n == k (mod d), and 0, otherwise. Then
%F a(n) = (2/5)*s(n,0,5) + (n-1)*(n-3)*((n-2)*(n-4) + 15)/240, if n is odd >= 5;
%F a(n) = (2/5)*s(n,0,5) + (n-2)*(n-4)*((n-1)*(n-3) + 15)/240, if n is even >= 5. (End)
%F a(n+5) = floor(n^4/240 + n^3/24 + 5*n^2/24 + 25*n/48 + 1 + (-1)^n*n/16). - _Robert Israel_, Jul 22 2015
%F a(n) = (A008646(n-5) + A119963(n, 5))/2 = (A008646(n-5) + C(floor((n-1)/2), 2))/2 for n >= 5. - _Petros Hadjicostas_, Jul 17 2018
%e From _Petros Hadjicostas_, Jul 17 2018: (Start)
%e Every n-bead bracelet of two colors such that 5 beads are black and n-5 are white can be transformed into a dihedral composition of n with 5 positive parts in the following way. Start with one B bead and go in one direction (say clockwise) until you reach the next B bead. Continue this process until you come back to the original B bead.
%e Let b_i be the number of beads from B bead i until you reach the last W bead before B bead i+1 (or B bead 1). Here, b_i = 1 iff there are no W beads between B bead i and B bead i+1 (or B bead 5 and B bead 1). Then b_1 + b_2 + b_3 + b_4 + b_5 = n, and we get a dihedral composition of n. (Of course, b_2 + b_3 + b_4 + b_5 + b_1 and b_5 + b_4 + b_3 + b_2 + b_1 belong to the same equivalence class of the dihedral composition b_1 + b_2 + b_3 + b_4 + b_5.)
%e For example, a(8) = 5, and we have the following bracelets with 5 B beads and 3 W beads. Next to the bracelets we list the corresponding dihedral compositions of n with k=5 parts (they must be viewed on a circle):
%e BBBBBWWW <-> 1+1+1+1+4
%e BBBBWBWW <-> 1+1+1+2+3
%e BBWBBBWW <-> 1+2+1+1+3
%e BWBBWBWB <-> 2+1+2+2+1
%e BWBWBWBB <-> 2+2+2+1+1
%e (End)
%p seq(floor(n^4/240 + n^3/24 + 5*n^2/24 + 25*n/48 + 1 + (-1)^n*n/16), n=0..100); # _Robert Israel_, Jul 22 2015
%t k = 5; 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 CoefficientList[Series[(1 - x + 2 x^3 - x^5 + x^6) / ((1 - x)^2 (1 - x^2)^2 (1 - x^5)), {x, 0, 50}], x] (* _Vincenzo Librandi_, Sep 07 2013 *)
%t k=5 (* Number of black beads in bracelet problem *); 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 *)
%o (PARI) a(n) = round((n^4 -10*n^3 +50*n^2 -(110+30*(1-n%2))*n)/240 +3/5) \\ _Washington Bomfim_, Jul 17 2008
%o (Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!(1-x+2*x^3-x^5+x^6)/((1-x)^2*(1-x^2)^2*(1-x^5))); // _Vincenzo Librandi_, Sep 07 2013
%Y Column k=5 of A052307.
%Y Cf. A005514, A008805, A032280, A032281, A032282, A292906.
%K nonn,easy,nice
%O 5,3
%A _Christian G. Bower_, _N. J. A. Sloane_
|
