OFFSET
5,3
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)
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. [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).
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
EXAMPLE
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)
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved