%I #89 Apr 04 2024 10:12:40
%S 0,0,1,1,2,4,5,7,10,12,15,19,22,26,31,35,40,46,51,57,64,70,77,85,92,
%T 100,109,117,126,136,145,155,166,176,187,199,210,222,235,247,260,274,
%U 287,301,316,330,345,361,376,392,409,425,442,460,477,495,514,532,551,571,590,610
%N a(n) = ceiling((n-3)(n-4)/6).
%C Number of solutions to x+y+z=0 (mod m) with 0<=x<=y<=z<m, where m = n-5.
%C Nonorientable genus of complete graph on n nodes.
%C Also (with different offset) Molien series for alternating group A_3.
%C (1+x^3 ) / ((1-x)*(1-x^2)*(1-x^3)) is the Poincaré series [or Poincare series] (or Molien series) for H^*(S_6, F_2).
%C a(n+5) is the number of necklaces with 3 black beads and n white beads.
%C The g.f./x^5 is Z(C_3,x), the 3-variate cycle index polynomial for the cyclic group C_3, with substitution x[i]->1/(1-x^i), i=1,2,3. Therefore by Polya enumeration a(n+5) is the number of cyclically inequivalent 3-necklaces whose 3 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... . See A102190 for Z(C_3,x). - _Wolfdieter Lang_, Feb 15 2005
%C a(n+1) is the number of pairs (x,y) with x and y in {0,...,n}, x = (y mod 3), and x+y < n. - _Clark Kimberling_, Jul 02 2012
%C From _Gus Wiseman_, Oct 17 2020: (Start)
%C Also the number of 3-part integer compositions of n - 2 that are either weakly increasing or strictly decreasing. For example, the a(5) = 1 through a(13) = 15 compositions are:
%C (111) (112) (113) (114) (115) (116) (117) (118) (119)
%C (122) (123) (124) (125) (126) (127) (128)
%C (222) (133) (134) (135) (136) (137)
%C (321) (223) (224) (144) (145) (146)
%C (421) (233) (225) (226) (155)
%C (431) (234) (235) (227)
%C (521) (333) (244) (236)
%C (432) (334) (245)
%C (531) (532) (335)
%C (621) (541) (344)
%C (631) (542)
%C (721) (632)
%C (641)
%C (731)
%C (821)
%C (End)
%D A. Adem and R. J. Milgram, Cohomology of Finite Groups, Springer-Verlag, 2nd. ed., 2004, p. 204.
%D D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 105.
%D J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see \bar{I}(n) p. 221.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 740.
%D E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, 2004.
%H T. D. Noe, <a href="/A007997/b007997.txt">Table of n, a(n) for n = 3..1000</a>
%H C. Ahmed, P. Martin, and V. Mazorchuk, <a href="http://arxiv.org/abs/1503.06718">On the number of principal ideals in d-tonal partition monoids</a>, arXiv preprint arXiv:1503.06718 [math.CO], 2015-2019.
%H Magnus Rahbek Hansen, <a href="https://www.maraha.dk/posts/2024/01/msc-thesis-invariant-theory-and-graph-theory/">Invariant Theory and Graphs</a>, Master's Thesis, Univ. Copenhagen (Denmark, 2023). See p. 38.
%H Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, <a href="https://arxiv.org/abs/2403.20148">A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions</a>, arXiv:2403.20148 [math.CO], 2024. See p. 6.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,1,-2,1).
%H <a href="/index/Mo#Molien">Index entries for Molien series</a>.
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>.
%F a(n) = a(n-3) + n - 2, a(0)=0, a(1)=0, a(2)=1 [Offset 0]. - _Paul Barry_, Jul 14 2004
%F G.f.: x^5*(1+x^3)/((1-x)*(1-x^2)*(1-x^3)) = x^5*(1-x+x^2)/((1-x)^2*(1-x^3)).
%F a(n+5) = Sum_{k=0..floor(n/2)} C(n-k,L(k/3)), where L(j/p) is the Legendre symbol of j and p. - _Paul Barry_, Mar 16 2006
%F a(3)=0, a(4)=0, a(5)=1, a(6)=1, a(7)=2, a(n) = 2*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) + a(n-5). - _Harvey P. Dale_, Jan 21 2014
%F a(n) = (n^2 - 7*n + 14 - 2*(-1)^(2^(n + 1 - 3*floor((n+1)/3))))/6. - _Luce ETIENNE_, Dec 27 2014
%F a(n) = A001399(n-3) + A001399(n-6). Compare to A140106(n) = A001399(n-3) - A001399(n-6). - _Gus Wiseman_, Oct 17 2020
%F a(n) = (40 + 3*(n - 7)*n - 4*cos(2*n*Pi/3) - 4*sqrt(3)*sin(2*n*Pi/3))/18. - _Stefano Spezia_, Dec 14 2021
%F Sum_{n>=5} 1/a(n) = 6 - 2*Pi/sqrt(3) + 2*Pi*tanh(sqrt(5/3)*Pi/2)/sqrt(15). - _Amiram Eldar_, Oct 01 2022
%e For m=7 (n=12), the 12 solutions are xyz = 000 610 520 511 430 421 331 322 662 653 644 554.
%p x^5*(1+x^3)/((1-x)*(1-x^2)*(1-x^3));
%p seq(ceil(binomial(n,2)/3), n=0..63); # _Zerinvary Lajos_, Jan 12 2009
%p a := n -> (n*(n-7)-2*([1,1,-1][n mod 3 +1]-7))/6;
%p seq(a(n), n=3..64); # _Peter Luschny_, Jan 13 2015
%t k = 3; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* _Robert A. Russell_, Sep 27 2004 *)
%t Table[Ceiling[((n-3)(n-4))/6],{n,3,100}] (* or *) LinearRecurrence[ {2,-1,1,-2,1},{0,0,1,1,2},100] (* _Harvey P. Dale_, Jan 21 2014 *)
%o (Haskell)
%o a007997 n = ceiling $ (fromIntegral $ (n - 3) * (n - 4)) / 6
%o a007997_list = 0 : 0 : 1 : zipWith (+) a007997_list [1..]
%o -- _Reinhard Zumkeller_, Dec 18 2013
%o (PARI) a(n)=(n^2-7*n+16)\6 \\ _Charles R Greathouse IV_, Sep 24 2015
%Y Cf. A000031, A007998, A003050, A047996, A048259, A053618.
%Y Apart from initial term, same as A058212.
%Y Cf. A000212, A000217, A001840, A128422, A156040.
%Y A001399(n-6)*2 = A069905(n-3)*2 = A211540(n-1)*2 counts the strict case.
%Y A014311 intersected with A225620 U A333256 ranks these compositions.
%Y A218004 counts these compositions of any length.
%Y A000009 counts strictly decreasing compositions.
%Y A000041 counts weakly increasing compositions.
%Y A001523 counts unimodal compositions, with complement counted by A115981.
%Y A007318 and A097805 count compositions by length.
%Y A032020 counts strict compositions, ranked by A233564.
%Y A333149 counts neither increasing nor decreasing strict compositions.
%Y Cf. A014311, A332834, A333147, A337481, A337482-A337484.
%K nonn,nice,easy
%O 3,5
%A _N. J. A. Sloane_