A128223 a(n) = if n mod 2 = 0 then n*(n+1)/2 otherwise (n+1)^2/2-1.

0, 1, 3, 7, 10, 17, 21, 31, 36, 49, 55, 71, 78, 97, 105, 127, 136, 161, 171, 199, 210, 241, 253, 287, 300, 337, 351, 391, 406, 449, 465, 511, 528, 577, 595, 647, 666, 721, 741, 799, 820, 881, 903, 967, 990, 1057, 1081, 1151, 1176, 1249, 1275, 1351, 1378, 1457, 1485

Offset: 0

Author

Gary W. Adamson, Feb 19 2007

Keywords

• nonn
• easy

Comments

a(n-1) is the length of the shortest path along the edges of the complete graph with n vertices. - Martin Fuller, Dec 06 2007

From Peter Kagey, Jan 25 2015: (Start)

For an irreflexive, non-transitive, symmetric relation, a(n) is the length of a relation chain required to demonstrate that a != b for all distinct elements a and b in S, where S contains n+1 elements.

For example, for the set {1,2,3} the chain requires a(2) = 3 relations (e.g., 1 != 2 != 3 != 1). For the set {1,2,3,4}, the chain requires a(3) = 7 relations (e.g., 1 != 2 != 3 != 4 != 1 != 3 != 2 != 4 -- noting the redundancy of 2!=3 and 3!=2). (End)

Given a set of n lots of n distinct items, it is possible to sort the items from fully collated (ABCABCABC) to fully sorted (AAABBBCCC), or vice versa, using a sorting algorithm whereby at each step a portion of the overall string is selected and its contents reversed. The minimum number of steps such an algorithm will take is a(n-1). For example, when n=3, a(n-1)=3: ABCABCABC -> ABBACBACC -> ABBAABCCC -> AAABBBCCC. - Elliott Line, Aug 02 2019

Examples

			a(5) = 17 = (5 + 1 + 5 + 1 + 5), row 5 of A128222.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Crossrefs

Row sums of A128222.

Cf. A024206, row sums of A128221 = A128174 * A127701.

Cf. A053439, A128221, A024206, A127701, A128174.

Programs

Haskell

a128223 n = if even n then n*(n + 1) `div` 2 else (n+1)^2 `div` 2 - 1 -- Peter Kagey, Jul 14 2015

Magma

[(-1+(-1)^n-(-3+(-1)^n)*n+2*n^2)/4: n in [0..60]]; // Vincenzo Librandi, Mar 18 2015

Maple

f:=n-> if n mod 2 = 0 then n*(n+1)/2 else (n+1)^2/2-1; fi;

Mathematica

f[n_] := If[EvenQ@ n, n (n + 1)/2, (n + 1)^2/2 - 1]; Array[f, 54] (* Michael De Vlieger, Mar 17 2015 *)
Table[(- 1 + (-1)^n - (- 3 + (-1)^n) n + 2 n^2) / 4, {n, 0, 60}] (* Vincenzo Librandi, Mar 18 2015 *)
CoefficientList[ Series[(-x - 2x^2 - 2x^3 + x^4)/((-1 + x)^3 (1 + x)^2), {x, 0, 54}], x] (* Robert G. Wilson v, Nov 16 2016 *)
LinearRecurrence[{1,2,-2,-1,1},{0,1,3,7,10},60] (* Harvey P. Dale, Mar 17 2020 *)

PARI

main(size)={my(n,m,v=vector(size),i);for(i=0,size-1,v[i+1]=if(i%2==0,i*(i+1)/2,(i+1)^2/2-1));return(v);} /* Anders Hellström, Jul 14 2015 */

Formula

a(n) = (-1+(-1)^n-(-3+(-1)^n)*n+2*n^2)/4. a(n) = a(n-1)+2*a(n-2)-2*a(n-3)-a(n-4)+a(n-5). G.f.: x*(x^3-2*x^2-2*x-1) / ((x-1)^3*(x+1)^2). - Colin Barker, Oct 16 2013

a(n) = A053439(n) - 1. - Peter Kagey, Nov 16 2016

Extensions

Edited by N. J. A. Sloane, Dec 06 2007