A032279 Number of bracelets (turnover necklaces) of n beads of 2 colors, 5 of them black.

1, 1, 3, 5, 10, 16, 26, 38, 57, 79, 111, 147, 196, 252, 324, 406, 507, 621, 759, 913, 1096, 1298, 1534, 1794, 2093, 2421, 2793, 3199, 3656, 4152, 4706, 5304, 5967, 6681, 7467, 8311, 9234, 10222, 11298, 12446, 13691, 15015, 16445

Offset: 5

Author

Christian G. Bower, N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of 5 beads each of them painted by one of n colors.

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.

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)

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

From Petros Hadjicostas, Jul 17 2018: (Start)

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.

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.

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.

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.)

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)

Examples

			From _Petros Hadjicostas_, Jul 17 2018: (Start)
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.
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.)
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):
BBBBBWWW <-> 1+1+1+1+4
BBBBWBWW <-> 1+1+1+2+3
BBWBBBWW <-> 1+2+1+1+3
BWBBWBWB <-> 2+1+2+2+1
BWBWBWBB <-> 2+2+2+1+1
(End)
		

References

• N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 5..1000
• Nesrine Benyahia-Tani, Zahra Yahi, and Sadek Bouroubi Ordered and non-ordered non-congruent convex quadrilaterals inscribed in a regular n-gon. Rostocker Math. Kolloq. 68, 71-79 (2013), Theorem 1.
• N. Benyahia Tani, Z. Yahi, and S. Bouroubi, Ordered and non-ordered non-isometric convex quadrilaterals inscribed in a regular n-gon, Bulletin du Laboratoire Liforce, 01 (2014) 1-9.
• C. G. Bower, Transforms (2)
• S. J. Cyvin, B. N. Cyvin, J. Brunvoll, I. Gutman, Chen Rong-si, S. El-Basil, and Zhang Fuji, Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem, Z. Naturforsch., 52a (1997), 867-873.
• J. L. Dunn and C. A. Bates, Analysis of the T1u(x)hg system as a model for C60 molecules, Phys. Rev. B 52, 5996, 15 August 1995.
• H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., Vol. 10, No. 8 (1979), 964-999.
• E. Kirkman, J. Kuzmanovich, and J. J. Zhang, Invariants of (-1)-Skew Polynomial Rings under Permutation Representations, arXiv preprint arXiv:1305.3973, 2013. See Example 5.5.
• Richard H. Reis, A formula for C(T) in Gupta's paper, Indian J. Pure and Appl. Math., Vol. 10 , No. 8 (1979), 1000-1001.
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., Vol. 35, No. 5 (2004), 629-638.
• Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., Vol. 35, No. 5 (2004), 629-638.
• Vladimir Shevelev, A problem of enumeration of two-color bracelets with several variations, arXiv:0710.1370 [math.CO], 2007-2011.
• Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
• Index entries for sequences related to bracelets
• Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,3,-3,-1,4,-1,-2,1).

Crossrefs

Column k=5 of A052307.

Cf. A005514, A008805, A032280, A032281, A032282, A292906.

Programs

Magma

m:=50; R:=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

Maple

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

Mathematica

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 *)
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 *)
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 *)

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

Formula

"DIK[ 5 ]" (necklace, indistinct, unlabeled, 5 parts) transform of 1, 1, 1, 1, ...

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

From Vladimir Shevelev, Apr 23 2011: (Start)

Put s(n,k,d)=1, if n == k (mod d), and 0, otherwise. Then

a(n) = (2/5)*s(n,0,5) + (n-1)*(n-3)*((n-2)*(n-4) + 15)/240, if n is odd >= 5;

a(n) = (2/5)*s(n,0,5) + (n-2)*(n-4)*((n-1)*(n-3) + 15)/240, if n is even >= 5. (End)

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

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