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

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

Offset: 0

Author

Jaroslav Krizek, Jun 16 2009

Keywords

• nonn
• easy

Comments

Essentially the same as A000217: zero followed by A000217. - Joerg Arndt, Jul 26 2015

Count of entries <= n in A003057.

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

Examples

			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}.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..10000
• Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 4.
• Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
• Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
• Steve Lawford and Yll Mehmeti, Cliques and a new measure of clustering: with application to U.S. domestic airlines, arXiv:1806.05866 [cs.SI], 2018.
• P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.
• Dennis Walsh, Notes on size-2 subsets of [n] that contain no consecutive integers
• Eric Weisstein's World of Mathematics, Composition
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A000124, A000217, A000290, A004125, A034856, A244049.

Programs

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

Maple

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

Mathematica

Join[{a = 0}, Table[a += n, {n, 0, 100}]] (* Vladimir Joseph Stephan Orlovsky, Jun 12 2011 *)
f[n_] := n(n-1)/2; Array[f, 54, 0] (* Robert G. Wilson v, Jul 26 2015 *)
Binomial[Range[0,60],2] (* or *) LinearRecurrence[{3,-3,1},{0,0,1},60] (* Harvey P. Dale, Apr 14 2017 *)

PARI

a(n)=n*(n-1)/2 \\ Charles R Greathouse IV, Jun 17 2017

Formula

a(n) = (n^2 - n)/2 = n*(n - 1)/2.

a(n) = A000124(n-1)-1 = A000217(n-1).

a(n) = a(n-1)+n-1 (with a(0)=a(1)=0). - Vincenzo Librandi, Nov 30 2010

Compositions: C(n,3) = binomial(n-1,n-3) = binomial(n-1,2), n>0. - Juergen Will, Jan 02 2015

G.f.: x^2/(1-x)^3. - Dennis P. Walsh, Mar 30 2011

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

a(n) = A244049(n+1) + A004125(n+1). - Omar E. Pol, Mar 25 2021

a(n) = A000290(n+1) - A034856(n+1). - Omar E. Pol, Mar 30 2021

E.g.f.: exp(x)*x^2/2. - Stefano Spezia, Dec 19 2021

Extensions

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