login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A161680 a(n) = binomial(n,2): number of size-2 subsets of {0,1,...,n} that contain no consecutive integers. 21
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

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..10000

Hsien-Kuei Hwang, S. Janson, 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, 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, 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).

FORMULA

a(n) = (n^2 - n)/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

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

Cf. A000124, A000217.

Sequence in context: A105339 A089594 A253145 * A000217 A105340 A176659

Adjacent sequences:  A161677 A161678 A161679 * A161681 A161682 A161683

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 21:27 EDT 2018. Contains 316327 sequences. (Running on oeis4.)