login
a(n) = ceiling(n^2/2).
(Formerly M1348 N0517)
111

%I M1348 N0517 #317 Sep 08 2024 10:21:19

%S 0,1,2,5,8,13,18,25,32,41,50,61,72,85,98,113,128,145,162,181,200,221,

%T 242,265,288,313,338,365,392,421,450,481,512,545,578,613,648,685,722,

%U 761,800,841,882,925,968,1013,1058,1105,1152,1201,1250,1301,1352,1405

%N a(n) = ceiling(n^2/2).

%C a(n) = number of pairs (i,j) in [1..n] X [1..n] with integral arithmetic mean. Cf. A132188, A362931. - _N. J. A. Sloane_, Aug 28 2023

%C Also, floor( (n^2+1)/2 ). - _N. J. A. Sloane_, Feb 08 2019

%C Floor(arithmetic mean of next n numbers). - _Amarnath Murthy_, Mar 11 2003

%C Pairwise sums of repeated squares (A008794).

%C Also, number of topologies on n+1 unlabeled elements with exactly 4 elements in the topology. a(3) gives 4 elements a,b,c,d; the valid topologies are (0,a,ab,abcd), (0,a,abc,abcd), (0,ab,abc,abcd), (0,a,bcd,abcd) and (0,ab,cd,abcd), with a count of 5. - _Jon Perry_, Mar 05 2004

%C Partition n into two parts, say, r and s, so that r^2 + s^2 is minimal, then a(n) = r^2 + s^2. Geometrical significance: folding a rod with length n units at right angles in such a way that the end points are at the least distance, which is given by a(n)^(1/2) as the hypotenuse of a right triangle with the sum of the base and height = n units. - _Amarnath Murthy_, Apr 18 2004

%C Convolution of A002061(n)-0^n and (-1)^n. Convolution of n (A001477) with {1,0,2,0,2,0,2,...}. Partial sums of repeated odd numbers {0,1,1,3,3,5,5,...}. - _Paul Barry_, Jul 22 2004

%C The ratio of the sum of terms over the total number of terms in an n X n spiral. The sum of terms of an n X n spiral is A037270, or Sum_{k=0..n^2} k = (n^4 + n^2)/2 and the total number of terms is n^2. - _William A. Tedeschi_, Feb 27 2008

%C Starting with offset 1 = row sums of triangle A158946. - _Gary W. Adamson_, Mar 31 2009

%C Partial sums of A109613. - _Reinhard Zumkeller_, Dec 05 2009

%C Also the number of compositions of even natural numbers into 2 parts < n. For example a(3)=5 are the compositions (0,0), (0,2), (2,0), (1,1), (2,2) of even natural numbers into 2 parts < 3. a(4)=8 are the compositions (0,0), (0,2), (2,0), (1,1), (2,2), (1,3), (3,1), (3,3) of even natural numbers into 2 parts < 4. - _Adi Dani_, Jun 05 2011

%C A001105 and A001844 interleaved. - _Omar E. Pol_, Sep 18 2011

%C Number of (w,x,y) having all terms in {0,...,n} and w=average(x,y). - _Clark Kimberling_, May 15 2012

%C For n > 0, minimum number of lines necessary to get through all unit cubes of an n X n X n cube (see Kantor link). - _Michel Marcus_, Apr 13 2013

%C Sum_{n > 0} 1/a(n) = Sum_{n > 0} 1/(2*n^2) + Sum_{n >= 0} 1/(2*n + 2*n^2 + 1) = (zeta(2) + (Pi* tanh(Pi/2)))/2 = 2.26312655.... - _Enrique Pérez Herrero_, Jun 17 2013

%C For n > 1, a(n) is the edge cover number of the n X n king graph. - _Eric W. Weisstein_, Jun 20 2017

%C Also the number of vertices in the n X n black bishop graph. - _Eric W. Weisstein_, Jun 26 2017

%C The same sequence arises in the triangular array of the integers >= 1, according to a simple "zig-zag" rule for selection of terms. a(n-1) lies in the (n-1)-th row of the array, and the second row of that sub-array (with apex a(n-1)) contains just two numbers, one odd, one even. The one with opposite parity to a(n-1) is a(n). - _David James Sycamore_, Jul 29 2018

%C Size of minimal ternary 1-covering code with code length n, i.e., K_n(3,1). See Kalbfleisch and Stanton. - _Patrick Wienhöft_, Jan 29 2019

%C For n > 1, a(n-1) is the maximum number of inversions in a permutation consisting of a single n-cycle on n symbols. - _M. Ryan Julian Jr._, Sep 10 2019

%C Also the number of classes of convex inscribed polyominoes in a (2,n) rectangular grid; two polyominoes are in the same class if one of them can be obtained by a reflection or 180-degree rotation of the other. - _Jean-Luc Manguin_, Jan 29 2020

%C a(n) is the number of pairs (p,q) such that 1 <= p, p+1 < q <= n+2 and q <> 2*p. - _César Eliud Lozada_, Oct 25 2020

%C a(n) is the maximum number of copies of a 12 permutation pattern in an alternating (or zig-zag) permutation of length n+1. The maximum number of copies of 123 in an alternating permutation is motivated in the Notices reference, and the argument here is analogous. - _Lara Pudwell_, Dec 01 2020

%C It appears that a(n) is the largest number of nodes of an induced path in the n X n king graph. An induced path going in a simple spiraling pattern, starting in a corner, has a(n) nodes. For even n this is optimal, because an induced path can have at most two nodes in any 2 X 2 subsquare. For odd n, I cannot see how to prove that (n^2+1)/2 is best possible. See also A357501. - _Pontus von Brömssen_, Oct 02 2022 [Proved by Beluhov (2023). - _Pontus von Brömssen_, Jan 30 2023]

%C a(n) = n + 2*(n-2) + 2*(n-4) + 2*(n-6) + ... number of black squares on an n X n chessboard. - _R. J. Mathar_, Dec 03 2022

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H Vincenzo Librandi, <a href="/A000982/b000982.txt">Table of n, a(n) for n = 0..3000</a>

%H Nikolai Beluhov, <a href="https://arxiv.org/abs/2301.01152">Snake paths in king and knight graphs</a>, arXiv:2301.01152 [math.CO], 2023.

%H M. Benoumhani and M. Kolli, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Benoumhani/benoumhani6.html">Finite topologies and partitions</a>, JIS 13 (2010) # 10.3.5, t_{N0}(n,4) in theorem 5.

%H Andrea C. Burgess, Caleb W. Jones, and David A. Pike, <a href="https://arxiv.org/abs/2403.01001">Extending Graph Burning to Hypergraphs</a>, arXiv:2403.01001 [math.CO], 2024. See p. 9.

%H Geoffrey B. Campbell, <a href="https://arxiv.org/abs/2302.01091">Vector Partition Identities for 2D, 3D and nD Lattices</a>, arXiv:2302.01091 [math.CO], 2023.

%H John Elias, <a href="/A000982/a000982.png">Illustration of Initial Terms: Intersection of a double spaced square grid and centrally aligned triangle</a>.

%H J. G. Kalbfleisch and R. G. Stanton, <a href="https://doi.org/10.1112/jlms/s1-44.1.60">A combinatorial problem in matching</a>, J. London Math. Soc. Vol. 1, No. 1 (1969), 60-64. [Corrected by _N. J. A. Sloane_, Feb 08 2019]

%H J. M. Kantor, <a href="http://hdl.handle.net/2042/32240">Mathématiques venues d'ailleurs: divertissements mathématiques en U.R.S.S.</a>, Le cube transpercé, pp. 56-62, Belin, Paris, 1982.

%H S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta, and K.M. Tamizhmani, <a href="http://arXiv.org/abs/nlin.SI/0104020">Blending two discrete integrability criteria: ...</a>, arXiv:nlin/0104020 [nlin.SI], 2001.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Lara Pudwell, <a href="https://www.ams.org/journals/notices/202007/rnoti-p994.pdf">From permutation patterns to the periodic table</a., Notices of the American Mathematical Society. 67.7 (2020), 994-1001.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BlackBishopGraph.html">Black Bishop Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCoverNumber.html">Edge Cover Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Topology.html">Topology</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCount.html">Vertex Count</a>

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

%F a(2*n) = 2*n^2, a(2*n+1) = 2*n^2 + 2*n + 1.

%F G.f.: -x*(1+x^2) / ( (1+x)*(x-1)^3 ). - _Simon Plouffe_ in his 1992 dissertation

%F From _Benoit Cloitre_, Nov 06 2002: (Start)

%F a(n) = (2*n^2 + 1 - (-1)^n) / 4.

%F a(0)=0, a(1)=1; for n>1, a(n+1) = n + 1 + max(2*floor(a(n)/2), 3*floor(a(n)/3)). (End)

%F G.f.: (x + x^2 + x^3 + x^4)/((1 - x)*(1 - x^2)^2), not reduced. - _Len Smiley_

%F a(n) = a(n-2) + 2n - 2. - _Paul Barry_, Jul 17 2004

%F From _Paul Barry_, Jul 22 2004: (Start)

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

%F a(n) = Sum_{k=0..n} (k^2 - k + 1 - 0^k)*(-1)^(n-k);

%F a(n) = Sum_{k=0..n} (1 + (-1)^(n-k) - 0^(n-k))*k. (End)

%F From _Reinhard Zumkeller_, Feb 27 2006: (Start)

%F a(0) = 0, a(n+1) = a(n) + 2*floor(n/2) + 1.

%F a(n) = A116940(n) - A005843(n). (End)

%F Starting with offset 1, = row sums of triangle A134444. Also, with offset 1, = binomial transform of [1, 1, 2, -2, 4, -8, 16, -32, ...]. - _Gary W. Adamson_, Oct 25 2007

%F a(n) = floor((n^2+1)/2). - _William A. Tedeschi_, Feb 27 2008

%F a(n) = A004526(n+1) + A000217(n-1). - _Yosu Yurramendi_, Sep 12 2008, corrected by _Klaus Purath_, Jun 15 2021

%F From _Jaume Oliver Lafont_, Dec 05 2008: (Start)

%F a(n) = a(n-1) + a(n-2) - a(n-3) + 2.

%F a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4). (End)

%F a(n) = A004526(n)^2 + A110654(n)^2. - _Philippe Deléham_, Mar 12 2009

%F a(n) = n^2 - floor(n^2/2). - _Wesley Ivan Hurt_, Jun 14 2013

%F Euler transform is length 4 sequence [2, 2, 0, -1].

%F a(n) = a(-n) for all n in Z. - _Michael Somos_, May 05 2015

%F a(n) is also the number of independent entries in a centrosymmetric n X n matrix: M(i, j) = M(n-i+1, n-j+1). - _Wolfdieter Lang_, Oct 12 2015

%F For n > 1, a(n+1)/a(n) = 3 - A081352(n-2)/a(n). - _Miko Labalan_, Mar 26 2016

%F E.g.f.: (1/2)*(x*(1 + x)*cosh(x) + (1 + x + x^2)*sinh(x)). - _Stefano Spezia_, Feb 03 2020

%F a(n) = binomial(n+1,2) - floor(n/2). - _César Eliud Lozada_, Oct 25 2020

%F From _Klaus Purath_, Jun 15 2021: (Start)

%F a(n-1) + a(n) = A002061(n).

%F a(n) = (a(n-1)^2 + 1) / a(n-2), n >= 3 odd.

%F a(n) = (a(n-1)^2 - (n-1)^2) / a(n-2), n >= 4 even. (End)

%e G.f. = x + 2*x^2 + 5*x^3 + 8*x^4 + 13*x^5 + 18*x^6 + 25*x^7 + 32*x^8 + ...

%e Centrosymmetric 3 X 3 matrix: [[a,b,c],[d,e,d],[c,b,a]], a(3) = 3*(3-1)/2 + (3-1)/2 + 1 = (3^2+1)/2 = 5 from a,b,c,d,e. 4 X 4 case: [[a,b,c,d],[e,f,g,h],[h,g,f,e],[d,c,b,a]], a(4) = 4*4/2 = 8. - _Wolfdieter Lang_, Oct 12 2015

%e a(3) = 5. The alternating permutation of length 3 + 1 = 4 with the maximum number of copies of 123 is 1324. The five copies are 12, 13, 14, 23, and 24. - _Lara Pudwell_, Dec 01 2020

%p seq( ceil(n^2/2),n=0..30) ; # _R. J. Mathar_, Jun 05 2011

%t Table[Ceiling[n^2/2], {n, 0, 120}] (* _Vladimir Joseph Stephan Orlovsky_, Apr 02 2011 *)

%t Accumulate[Join[{0}, (# - Boole[EvenQ[#]] &) /@ Range[80]]] (* _Alonso del Arte_, Sep 11 2019 *)

%o (Magma) [(2*n^2 + 1 - (-1)^n) / 4: n in [0..60]]; // _Vincenzo Librandi_, Jun 16 2011

%o (Haskell)

%o a000982 = (`div` 2) . (+ 1) . (^ 2) -- _Reinhard Zumkeller_, Jun 27 2013

%o (PARI) a(n)=(n^2+1)\2 \\ _Charles R Greathouse IV_, Sep 13 2013

%o (PARI) x='x+O('x^100); concat([0], Vec(x*(1+x^2)/((1+x)*(1-x)^3))) \\ _Altug Alkan_, Oct 12 2015

%o (PARI) apply( A000982(n)=n^2\/2, [0..55]) \\ _M. F. Hasler_, Feb 29 2020

%o (Scala) (((1 to 49) by 2) flatMap { List.fill(2)(_) }).scanLeft(0)(_ + _) // _Alonso del Arte_, Sep 11 2019

%o (Python)

%o def A000982(n): return n**2+1>>1 # _Chai Wah Wu_, Aug 28 2023

%Y Cf. A000096, A000217, A001105, A001477, A001844, A002061, A004526, A005843, A007590, A008794, A037270, A081352, A109613, A110654, A116940, A134444, A158946, A168380, A357501.

%Y Column 2 of A195040.

%Y Cf. also A132188, A362931.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_