A005232 Expansion of (1-x+x^2)/((1-x)^2*(1-x^2)*(1-x^4)). (Formerly M2346)

1, 1, 3, 4, 8, 10, 16, 20, 29, 35, 47, 56, 72, 84, 104, 120, 145, 165, 195, 220, 256, 286, 328, 364, 413, 455, 511, 560, 624, 680, 752, 816, 897, 969, 1059, 1140, 1240, 1330, 1440, 1540, 1661, 1771, 1903, 2024, 2168, 2300, 2456, 2600, 2769, 2925, 3107, 3276

Offset

0,3

Comments

Also number of n X 2 binary matrices under row and column permutations and column complementations (if offset is 0).

Also Molien series for certain 4-D representation of dihedral group of order 8.

With offset 4, number of bracelets (turnover necklaces) of n-bead of 2 colors with 4 red beads. - Washington Bomfim, Aug 27 2008

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of 4 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=4 (see our comment to A032279). (End)

Number of 2 X 2 matrices with nonnegative integer values totaling n under row and column permutations. - Gabriel Burns, Nov 08 2016

From Petros Hadjicostas, Jan 12 2019: (Start)

By "necklace", Vladimir Shevelev (above) means "turnover necklace", i.e., a bracelet. Zagaglia Salvi (1999) also uses this terminology: she calls a bracelet "necklace" and a necklace "cycle".

According to Cyvin et al. (1997), the sequence (a(n): n >= 0) consists of "the total numbers of isomers of polycyclic conjugated hydrocarbons with q + 1 rings and q internal carbons in one ring (class Q_q)", where q = 4 and n is the hydrogen content (i.e., we count certain isomers of C_{n+2*q} H_n with q = 4 and n >= 0). (End)

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Links

T. D. Noe, Table of n, a(n) for n = 0..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.

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.

S. N. Ethier and S. E. Hodge, Identity-by-descent analysis of sibship configurations, Amer. J. Medical Genetics, 22 (1985), 263-272.

H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.

W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 1-15.

W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)

M. Klemm, Selbstduale Codes über dem Ring der ganzen Zahlen modulo 4, Arch. Math. (Basel), 53 (1989), 201-207.

P. Lisonek, Quasi-polynomials: A case study in experimental combinatorics, RISC-Linz Report Series No. 93-18, 1983. (Annotated scanned copy)

G. Nebe, E. M. Rains and N. J. A. Sloane, Self-Dual Codes and Invariant Theory, Springer, Berlin, 2006.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

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., 35 (2004), no. 5, 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) (Cf. Section 5), arXiv:1104.4051 [math.CO], 2011.

Index entries for sequences related to bracelets

Index entries for Molien series

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,2,-2,0,2,-1).

Formula

G.f.: (1+x^3)/((1-x)*(1-x^2)^2*(1-x^4)).

G.f.: (1/8)*(1/(1-x)^4+3/(1-x^2)^2+2/(1-x)^2/(1-x^2)+2/(1-x^4)). - Vladeta Jovovic, Aug 05 2000

Euler transform of length 6 sequence [ 1, 2, 1, 1, 0, -1 ]. - Michael Somos, Feb 01 2007

a(2n+1) = A006918(2n+2)/2;

a(2n) = (A006918(2n+1) + A008619(n))/2.

a(n) = -a(-6 - n) for all n in Z. - Michael Somos, Feb 05 2011

From Vladimir Shevelev, Apr 22 2011: (Start)

if n == 0 (mod 4), then a(n) = n*(n^2-3*n+8)/48;

if n == 1, 3 (mod 4), then a(n) = (n^2-1)*(n-3)/48;

if n == 2 (mod 4), then a(n) = (n-2)*(n^2-n+6)/48. (End)

a(n) = 2*a(n-1) - 2*a(n-3) + 2*a(n-4) - 2*a(n-5) + 2*a(n-7) - a(n-8) with a(0) = 1, a(1) = 1, a(2) = 3, a(3) = 4, a(4) = 8, a(5) = 10, a(6) = 16, a(7) = 20. - Harvey P. Dale, Oct 24 2012

a(n) = ((n+3)*(2*n^2+12*n+19+9*(-1)^n) + 6*(-1)^((2*n-1+(-1)^n)/4)*(1+(-1)^n))/96. - Luce ETIENNE, Mar 16 2015

a(n) = |A128498(n)| + |A128498(n-3)|. - R. J. Mathar, Jun 11 2019

Example

G.f. = 1 + x + 3*x^2 + 4*x^3 + 8*x^4 + 10*x^5 + 16*x^6 + 20*x^7 + 29*x^8 + ...
There are 8 4 X 2 matrices up to row and column permutations and column complementations:
  [1 1] [1 0] [1 0] [0 1] [0 1] [0 1] [0 1] [0 0]
  [1 1] [1 1] [1 0] [1 0] [1 0] [1 0] [0 1] [0 1]
  [1 1] [1 1] [1 1] [1 1] [1 0] [1 0] [1 0] [1 0]
  [1 1] [1 1] [1 1] [1 1] [1 1] [1 0] [1 0] [1 1].
There are 8 2 X 2 matrices of nonnegative integers totaling 4 up to row and column permutations:
  [4 0] [3 1] [2 2] [2 1] [2 1] [3 0] [2 0] [1 1]
  [0 0] [0 0] [0 0] [0 1] [1 0] [1 0] [2 0] [1 1].

Maple

A005232:=-(-1-z-2*z**3+2*z**2+z**7-2*z**6+2*z**4)/(z**2+1)/(1+z)**2/(z-1)**4; # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence apart from an initial 1

Mathematica

k = 4; 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 + x^2)/((1 - x)^2(1 - x^2)(1 - x^4)), {x, 0, 51}], x] (* Robert G. Wilson v, Mar 29 2006 *)
LinearRecurrence[{2, 0, -2, 2, -2, 0, 2, -1}, {1, 1, 3, 4, 8, 10, 16, 20}, 60] (* Harvey P. Dale, Oct 24 2012 *)
k=4 (* Number of red beads in bracelet problem *); CoefficientList[Series[(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) = (n^3 + 9*n^2 + (32-9*(n%2))*n + [48, 15, 36, 15][n%4+1]) / 48}; \\ Michael Somos, Feb 01 2007
(PARI) {a(n) = my(s=1); if( n<-5, n = -6-n; s=-1); if( n<0, 0, s * polcoeff( (1 - x + x^2) / ((1 - x)^2 * (1 - x^2) * (1 - x^4)) + x * O(x^n), n))}; \\ Michael Somos, Feb 01 2007
(PARI) a(n) = round((n^3 +9*n^2 +(32-9*(n%2))*n)/48 +0.6) \\ Washington Bomfim, Jul 17 2008
(PARI) a(n) = ceil((n+1)*(2*n^2+16*n+39+9*(-1)^n)/96) \\ Tani Akinari, Aug 23 2013
(Python) a=lambda n: sum((k//2+1)*((n-k)//2+1) for k in range((n-1)//2+1))+(n+1)%2*(((n//4+1)*(n//4+2))//2)  # Gabriel Burns, Nov 08 2016

Crossrefs

Row n=2 of A343875.

Column k=4 of A052307.

Cf. A006381, A006382, A008805.

Sequence in context: A308844 A131355 A092534 * A165272 A310010 A294085

Adjacent sequences: A005229 A005230 A005231 * A005233 A005234 A005235

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Sequence extended by Christian G. Bower

Status

approved