OFFSET
0,3
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
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).
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
EXAMPLE
a(5) = 17 = (5 + 1 + 5 + 1 + 5), row 5 of A128222.
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 *)
PROG
(Magma) [(-1+(-1)^n-(-3+(-1)^n)*n+2*n^2)/4: n in [0..60]]; // Vincenzo Librandi, Mar 18 2015
(Haskell) a128223 n = if even n then n*(n + 1) `div` 2 else (n+1)^2 `div` 2 - 1 -- Peter Kagey, Jul 14 2015
(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 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Gary W. Adamson, Feb 19 2007
EXTENSIONS
Edited by N. J. A. Sloane, Dec 06 2007
STATUS
approved