|
|
A032279
|
|
Number of bracelets (turnover necklaces) of n beads of 2 colors, 5 of them black.
|
|
14
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
5,3
|
|
COMMENTS
|
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
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
|
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.
|
|
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
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
|
|
EXAMPLE
|
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
|
|
|
|