A006918 - OEIS

A006918

a(n) = binomial(n+3, 3)/4 for odd n, n*(n+2)*(n+4)/24 for even n.
(Formerly M1349)

102

%I M1349 #199 Jan 24 2025 18:36:53

%S 0,1,2,5,8,14,20,30,40,55,70,91,112,140,168,204,240,285,330,385,440,

%T 506,572,650,728,819,910,1015,1120,1240,1360,1496,1632,1785,1938,2109,

%U 2280,2470,2660,2870,3080,3311,3542,3795,4048,4324,4600,4900,5200,5525,5850,6201,6552,6930

%N a(n) = binomial(n+3, 3)/4 for odd n, n*(n+2)*(n+4)/24 for even n.

%C Maximal number of inconsistent triples in a tournament on n+2 nodes [Kac]. - corrected by _Leen Droogendijk_, Nov 10 2014

%C a(n-4) is the number of aperiodic necklaces (Lyndon words) with 4 black beads and n-4 white beads.

%C a(n-3) is the maximum number of squares that can be formed from n lines, for n>=3. - _Erich Friedman_; corrected by _Leen Droogendijk_, Nov 10 2014

%C Number of trees with diameter 4 where at most 2 vertices 1 away from the graph center have degree > 2. - _Jon Perry_, Jul 11 2003

%C a(n+1) is the number of partitions of n into parts of two kinds, with at most two parts of each kind. Also a(n-3) is the number of partitions of n with Durfee square of size 2. - _Franklin T. Adams-Watters_, Jan 27 2006

%C Factoring the g.f. as x/(1-x)^2 times 1/(1-x^2)^2 we find that the sequence equals (1, 2, 3, 4, ...) convolved with (1, 0, 2, 0, 3, 0, 4, ...), A000027 convolved with its aerated variant. - _Gary W. Adamson_, May 01 2009

%C Starting with "1" = triangle A171238 * [1,2,3,...]. - _Gary W. Adamson_, Dec 05 2009

%C The Kn21, Kn22, Kn23, Fi2 and Ze2 triangle sums, see A180662 for their definitions, of the Connell-Pol triangle A159797 are linear sums of shifted versions of this sequence, e.g., Kn22(n) = a(n+1) + a(n) + 2*a(n-1) + a(n-2) and Fi2(n) = a(n) + 4*a(n-1) + a(n-2). - _Johannes W. Meijer_, May 20 2011

%C For n>3, a(n-4) is the number of (w,x,y,z) having all terms in {1,...,n} and w+x+y+z=|x-y|+|y-z|. - _Clark Kimberling_, May 23 2012

%C a(n) is the number of (w,x,y) having all terms in {0,...,n} and w+x+y < |w-x|+|x-y|. - _Clark Kimberling_, Jun 13 2012

%C For n>0 number of inequivalent (n-1) X 2 binary matrices, where equivalence means permutations of rows or columns or the symbol set. - _Alois P. Heinz_, Aug 17 2014

%C Number of partitions p of n+5 such that p[3] = 2. Examples: a(1)=1 because we have (2,2,2); a(2)=2 because we have (2,2,2,1) and (3,2,2); a(3)=5 because we have (2,2,2,1,1), (2,2,2,2), (3,2,2,1), (3,3,2), and (4,2,2). See the R. P. Stanley reference. - _Emeric Deutsch_, Oct 28 2014

%C Sum over each antidiagonal of A243866. - _Christopher Hunt Gribble_, Apr 02 2015

%C Number of nonisomorphic outer planar graphs of order n>=3, size n+2, and maximum degree 3. - _Christian Barrientos_ and _Sarah Minion_, Feb 27 2018

%C a(n) is the number of 2413-avoiding odd Grassmannian permutations of size n+1. - _Juan B. Gil_, Mar 09 2023

%D J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 147.

%D M. Kac, An example of "counting without counting", Philips Res. Reports, 30 (1975), 20*-22* [Special issue in honour of C. J. Bouwkamp].

%D E. V. McLaughlin, Numbers of factorizations in non-unique factorial domains, Senior Thesis, Allegeny College, Meadville, PA, 2004.

%D K. B. Reid and L. W. Beineke "Tournaments", pp. 169-204 in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978, p. 186, Theorem 6.11.

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

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 2nd ed., 2012, Exercise 4.16, pp. 530, 552.

%D W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 33.

%H T. D. Noe, <a href="/A006918/b006918.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Luc Baril, Alexander Burstein, and Sergey Kirgizov, <a href="https://arxiv.org/abs/2010.06270">Pattern statistics in faro words and permutations</a>, arXiv:2010.06270 [math.CO], 2020.

%H D. J. Broadhurst, <a href="http://arXiv.org/abs/hep-th/9604128">On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory</a>, arXiv:hep-th/9604128, 1996.

%H Y. Choliy and A. V. Sills, <a href="http://home.dimacs.rutgers.edu/~asills/Durfee/CholiySillsRevAOC.pdf">A formula for the partition function that “counts”</a>, Preprint 2015.

%H L. Colmenarejo, <a href="http://arxiv.org/abs/1604.00803">Combinatorics on several families of Kronecker coefficients related to plane partitions</a>, arXiv:1604.00803 [math.CO], 2016. See Table 1 p. 5.

%H S. J. Cyvin et al., <a href="http://zfn.mpdl.mpg.de/data/Reihe_A/52/ZNA-1997-52a-0867.pdf">Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem</a>, Z. Naturforsch., 52a (1997), 867-873.

%H Steven Edwards and William Griffiths, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-4/EdwardsGriffiths82617.pdf">Generalizations of Delannoy and cross polytope numbers</a>, Fib. Q., Vol. 55, No. 4 (2017), pp. 356-366.

%H B. G. Eke, <a href="http://dx.doi.org/10.1016/0012-365X(74)90082-X">Monotonic triads</a>, Discrete Math., Vol. 9, No. 4 (1974), pp. 359-363. MR0354390 (50 #6869)

%H Irene Erazo, John López, and Carlos Trujillo, <a href="https://revistas.unal.edu.co/index.php/recolma/article/view/85538">A combinatorial problem that arose in integer B_3 Sets</a>, Revista Colombiana de Matemáticas, Vol. 53, No. 2 (2019), pp. 195-203.

%H Juan B. Gil and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2207.12617">Pattern-avoiding even and odd Grassmannian permutations</a>, arXiv:2207.12617 [math.CO], 2022.

%H John Golden and Marcus Spradlin, <a href="http://arxiv.org/abs/1203.1915">Collinear and Soft Limits of Multi-Loop Integrands in N= 4 Yang-Mills</a>, arXiv preprint arXiv:1203.1915 [hep-th], 2012. - From _N. J. A. Sloane_, Sep 14 2012

%H Michele Graffeo, Sergej Monavari, Riccardo Moschetti, and Andrea T. Ricolfi, <a href="https://arxiv.org/abs/2501.10267">Enumeration of partitions via socle reduction</a>, arXiv:2501.10267 [math.CO], 2025. See p. 40.

%H Brian Hopkins and Aram Tangboonduangjit, <a href="https://arxiv.org/abs/2412.11528">Water Cells in Compositions of 1s and 2s</a>, arXiv:2412.11528 [math.CO], 2024. See p. 3.

%H Brian O'Sullivan and Thomas Busch, <a href="http://arxiv.org/abs/0810.0231">Spontaneous emission in ultra-cold spin-polarised anisotropic Fermi seas</a>, arXiv 0810.0231v1 [quant-ph], 2008. [Eq 10b, lambda=2]

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-4,1,2,-1).

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>.

%F G.f.: x/((1-x)^2*(1-x^2)^2) = x/((1+x)^2*(1-x)^4).

%F 0, 0, 0, 1, 2, 5, 8, 14, ... has a(n) = (Sum_{k=0..n} floor(k(n-k)/2))/2. - _Paul Barry_, Sep 14 2003

%F 0, 0, 0, 0, 0, 1, 2, 5, 8, 14, 20, 30, 40, 55, ... has a(n) = binomial(floor(1/2 n), 3) + binomial(floor(1/2 n + 1/2), 3) [Eke]. - _N. J. A. Sloane_, May 12 2012

%F a(0)=0, a(1)=1, a(n) = (2/(n-1))*a(n-1) + ((n+3)/(n-1))*a(n-2). - _Benoit Cloitre_, Jun 28 2004

%F a(n) = floor(binomial(n+4, 4)/(n+4)) - floor((n+2)/8)(1+(-1)^n)/2. - _Paul Barry_, Jan 01 2005

%F a(n+1) = a(n) + binomial(floor(n/2)+2,2), i.e., first differences are A008805. Convolution of A008619 with itself, then shifted right (or A004526 with itself, shifted left by 3). - _Franklin T. Adams-Watters_, Jan 27 2006

%F a(n+1) = (A027656(n) + A003451(n+5))/2 with a(1)=0. - _Yosu Yurramendi_, Sep 12 2008

%F Linear recurrence: a(n) = 2a(n-1) + a(n-2) - 4a(n-3) + a(n-4) + 2a(n-5) - a(n-6). - _Jaume Oliver Lafont_, Dec 05 2008

%F Euler transform of length 2 sequence [2, 2]. - _Michael Somos_, Aug 15 2009

%F a(n) = -a(-4-n) for all n in Z.

%F a(n+1) + a(n) = A002623(n). - _Johannes W. Meijer_, May 20 2011

%F a(n) = (n+2)*(2*n*(n+4)-3*(-1)^n+3)/48. - _Bruno Berselli_, May 21 2011

%F a(2n) = A007290(n+2). - _Jon Perry_, Nov 10 2014

%F G.f.: (1/(1-x)^4-1/(1-x^2)^2)/4. - _Herbert Kociemba_, Oct 23 2016

%F E.g.f.: (x*(18 + 9*x + x^2)*cosh(x) + (6 + 15*x + 9*x^2 + x^3)*sinh(x))/24. - _Stefano Spezia_, Dec 07 2021

%F From _Amiram Eldar_, Mar 20 2022: (Start)

%F Sum_{n>=1} 1/a(n) = 75/4 - 24*log(2).

%F Sum_{n>=1} (-1)^(n+1)/a(n) = 69/4 - 24*log(2). (End)

%e G.f. = x + 2*x^2 + 5*x^3 + 8*x^4 + 14*x^5 + 20*x^6 + 30*x^7 + 40*x^8 + 55*x^9 + ...

%e From _Gus Wiseman_, Apr 06 2019: (Start)

%e The a(4 - 3) = 1 through a(8 - 3) = 14 integer partitions with Durfee square of length 2 are the following (see Franklin T. Adams-Watters's second comment). The Heinz numbers of these partitions are given by A325164.

%e (22) (32) (33) (43) (44)

%e (221) (42) (52) (53)

%e (222) (322) (62)

%e (321) (331) (332)

%e (2211) (421) (422)

%e (2221) (431)

%e (3211) (521)

%e (22111) (2222)

%e (3221)

%e (3311)

%e (4211)

%e (22211)

%e (32111)

%e (221111)

%e The a(0 + 1) = 1 through a(4 + 1) = 14 integer partitions of n into parts of two kinds with at most two parts of each kind are the following (see Franklin T. Adams-Watters's first comment).

%e ()() ()(1) ()(2) ()(3) ()(4)

%e (1)() (2)() (3)() (4)()

%e ()(11) (1)(2) (1)(3)

%e (1)(1) ()(21) ()(22)

%e (11)() (2)(1) (2)(2)

%e (21)() (22)()

%e (1)(11) ()(31)

%e (11)(1) (3)(1)

%e (31)()

%e (11)(2)

%e (1)(21)

%e (2)(11)

%e (21)(1)

%e (11)(11)

%e The a(6 - 5) = 1 through a(10 - 5) = 14 integer partitions whose third part is 2 are the following (see Emeric Deutsch's comment). The Heinz numbers of these partitions are given by A307373.

%e (222) (322) (332) (432) (442)

%e (2221) (422) (522) (532)

%e (2222) (3222) (622)

%e (3221) (3321) (3322)

%e (22211) (4221) (4222)

%e (22221) (4321)

%e (32211) (5221)

%e (222111) (22222)

%e (32221)

%e (33211)

%e (42211)

%e (222211)

%e (322111)

%e (2221111)

%e (End)

%p with(combstruct):ZL:=[st,{st=Prod(left,right),left=Set(U,card=r),right=Set(U,card=r),U=Sequence(Z,card>=3)}, unlabeled]: subs(r=1,stack): seq(count(subs(r=2,ZL),size=m),m=11..58) ; # _Zerinvary Lajos_, Mar 09 2007

%p A006918 := proc(n)

%p if type(n,'even') then

%p n*(n+2)*(n+4)/24 ;

%p else

%p binomial(n+3,3)/4 ;

%p fi ;

%p end proc: # _R. J. Mathar_, May 17 2016

%t f[n_]:=If[EvenQ[n],(n(n+2)(n+4))/24,Binomial[n+3,3]/4]; Join[{0},Array[f,60]] (* _Harvey P. Dale_, Apr 20 2011 *)

%t durf[ptn_]:=Length[Select[Range[Length[ptn]],ptn[[#]]>=#&]];

%t Table[Length[Select[IntegerPartitions[n],durf[#]==2&]],{n,0,30}] (* _Gus Wiseman_, Apr 06 2019 *)

%o (PARI) { parttrees(n)=local(pt,k,nk); if (n%2==0, pt=(n/2+1)^2, pt=ceil(n/2)*(ceil(n/2)+1)); pt+=floor(n/2); for (x=1,floor(n/2),pt+=floor(x/2)+floor((n-x)/2)); if (n%2==0 && n>2, pt-=floor(n/4)); k=1; while (3*k<=n, for (x=k,floor((n-k)/2), pt+=floor(k/2); if (x!=k, pt+=floor(x/2)); if ((n-x-k)!=k && (n-x-k)!=x, pt+=floor((n-x-k)/2))); k++); pt }

%o (PARI) {a(n) = n += 2; (n^3 - n * (2-n%2)^2) / 24}; /* _Michael Somos_, Aug 15 2009 */

%o (Haskell)

%o a006918 n = a006918_list !! n

%o a006918_list = scanl (+) 0 a008805_list

%o -- _Reinhard Zumkeller_, Feb 01 2013

%o (Magma) [Floor(Binomial(n+4, 4)/(n+4))-Floor((n+2)/8)*(1+(-1)^n)/2: n in [0..60]]; // _Vincenzo Librandi_, Nov 10 2014

%Y Cf. A000031, A001037, A028723, A051168. a(n) = T(n,4), array T as in A051168.

%Y Cf. A000094.

%Y Cf. A171238. - _Gary W. Adamson_, Dec 05 2009

%Y Row sums of A173997. - _Gary W. Adamson_, Mar 05 2010

%Y Column k=2 of A242093. Column k=2 of A115720 and A115994.

%Y Cf. A117485, A257990, A307373, A325164, A325168.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_