

A161680


a(n) = binomial(n,2): number of size2 subsets of {0,1,...,n} that contain no consecutive integers.


53



0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

a(n) is the number of size2 subsets of [n+1] that contain no consecutive integers, a(n+1) is the nth triangular number.  Dennis P. Walsh, Mar 30 2011
Construct the nth row of Pascal's triangle (A007318) from the preceding row, starting with row 0 = 1. a(n) is the sequence consisting of the total number of additions required to compute the triangle in this way up to row n. Copying a term does not count as an addition.  Douglas Latimer, Mar 05 2012
a(n1) is also the number of ordered partitions (compositions) of n >= 1 into exactly 3 parts.  Juergen Will, Jan 02 2016
a(n+2) is also the number of weak compositions (ordered weak partitions) of n into exactly 3 parts.  Juergen Will, Jan 19 2016
In other words, this is the number of relations between entities, for example between persons: Two persons (n = 2) will have one relation (a(n) = 1), whereas four persons will have six relations to each other, and 20 persons will have 190 relations between them.  Halfdan Skjerning, May 03 2017
This also describes the largest number of intersections between n lines of equal length sequentially connected at (n1) joints. The joints themselves do not count as intersection points.  Joseph Rozhenko, Oct 05 2021
The lexicographically earliest infinite sequence of nonnegative integers with monotonically increasing differences (that are also nonnegative integers).  Joe B. Stephen, Jul 22 2023
It appears that a(n) is the maximal number of comparisons needed for sorting n elements by any of the Bubble, Insertion, or Quicksort algorithms.  Darío Clavijo, Aug 12 2023


LINKS



FORMULA

a(n) = (n^2  n)/2 = n*(n  1)/2.
Compositions: C(n,3) = binomial(n1,n3) = binomial(n1,2), n>0.  Juergen Will, Jan 02 2015
G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1x))^3.  Juergen Will, Jan 02 2015
a(n1) = 6*n*s(1,n), n >= 1, where s(h,k) are the Dedekind sums. For s(1,n) see A264388(n)/A264389(n), also for references.  Wolfdieter Lang, Jan 11 2016


EXAMPLE

A003057 starts 2, 3, 3, 4, 4,..., so there are a(0)=0 numbers <= 0, a(1)=0 numbers <= 1, a(2)=1 number <= 2, a(3)=3 numbers <= 3 in A003057.
For n=4, a(4)=6 since there are exactly 6 size2 subsets of {0,1,2,3,4} that contain no consecutive integers, namely, {0,2}, {0,3}, {0,4}, {1,3}, {1,4}, and {2,4}.


MAPLE

seq(binomial(n, 2), n=0..50);


MATHEMATICA

Binomial[Range[0, 60], 2] (* or *) LinearRecurrence[{3, 3, 1}, {0, 0, 1}, 60] (* Harvey P. Dale, Apr 14 2017 *)


PROG

(Magma) a003057:=func< n  Round(Sqrt(2*(n1)))+1 >; S:=[]; m:=2; count:=0; for n in [2..2000] do if a003057(n) lt m then count+:=1; else Append(~S, count); m+:=1; end if; end for; S; // Klaus Brockhaus, Nov 30 2010


CROSSREFS



KEYWORD

nonn,easy,changed


AUTHOR



EXTENSIONS

Definition rephrased, offset set to 0 by R. J. Mathar, Aug 03 2010


STATUS

approved



