|
| |
|
|
A128223
|
|
a(n) = if n mod 2 = 0 then n*(n+1)/2 otherwise (n+1)^2/2-1.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
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
|
|
|
|
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
|
|
|
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
