|
| |
|
|
A161680
|
|
a(n) = binomial(n,2): number of size-2 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 size-2 subsets of [n+1] that contain no consecutive integers, a(n+1) is the n-th triangular number. - Dennis P. Walsh, Mar 30 2011
Construct the n-th 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(n-1) 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 (n-1) 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(n-1,n-3) = binomial(n-1,2), n>0. - Juergen Will, Jan 02 2015
G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1-x))^3. - Juergen Will, Jan 02 2015
a(n-1) = 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 size-2 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*(n-1)))+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
|
| |
|
|
