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

%I #65 Sep 08 2022 08:45:30

%S 0,1,3,7,10,17,21,31,36,49,55,71,78,97,105,127,136,161,171,199,210,

%T 241,253,287,300,337,351,391,406,449,465,511,528,577,595,647,666,721,

%U 741,799,820,881,903,967,990,1057,1081,1151,1176,1249,1275,1351,1378,1457,1485

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

%C 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

%C From _Peter Kagey_, Jan 25 2015: (Start)

%C 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.

%C 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)

%C 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

%H Peter Kagey, <a href="/A128223/b128223.txt">Table of n, a(n) for n = 0..1000</a>

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

%F 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

%F a(n) = A053439(n) - 1. - _Peter Kagey_, Nov 16 2016

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

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

%t f[n_] := If[EvenQ@ n, n (n + 1)/2, (n + 1)^2/2 - 1]; Array[f, 54] (* _Michael De Vlieger_, Mar 17 2015 *)

%t Table[(- 1 + (-1)^n - (- 3 + (-1)^n) n + 2 n^2) / 4, {n, 0, 60}] (* _Vincenzo Librandi_, Mar 18 2015 *)

%t 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 *)

%t LinearRecurrence[{1,2,-2,-1,1},{0,1,3,7,10},60] (* _Harvey P. Dale_, Mar 17 2020 *)

%o (Magma) [(-1+(-1)^n-(-3+(-1)^n)*n+2*n^2)/4: n in [0..60]]; // _Vincenzo Librandi_, Mar 18 2015

%o (Haskell) a128223 n = if even n then n*(n + 1) `div` 2 else (n+1)^2 `div` 2 - 1 -- _Peter Kagey_, Jul 14 2015

%o (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 */

%Y Row sums of A128222.

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

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

%K nonn,easy

%O 0,3

%A _Gary W. Adamson_, Feb 19 2007

%E Edited by _N. J. A. Sloane_, Dec 06 2007