OFFSET

0,4

COMMENTS

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

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.

Eric Weisstein's World of Mathematics, Composition

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

FORMULA

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

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

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

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

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 *)

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

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

CROSSREFS

KEYWORD

nonn,easy

AUTHOR

Jaroslav Krizek, Jun 16 2009

EXTENSIONS

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

STATUS

approved