The OEIS is supported by the many generous donors to the OEIS Foundation. 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. 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 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 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 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). 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 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, A000290, A004125, A034856, A244049. Sequence in context: A105339 A089594 A253145 * A000217 A179865 A105340 Adjacent sequences: A161677 A161678 A161679 * A161681 A161682 A161683 KEYWORD nonn,easy,changed 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 22 16:46 EDT 2023. Contains 365531 sequences. (Running on oeis4.)