cp's OEIS Frontend

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

%I A161680 #159 Feb 16 2025 08:33:10
%S A161680 0,0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,
%T A161680 231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,
%U A161680 741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378
%N A161680 a(n) = binomial(n,2): number of size-2 subsets of {0,1,...,n} that contain no consecutive integers.
%C A161680 Essentially the same as A000217: zero followed by A000217. - _Joerg Arndt_, Jul 26 2015
%C A161680 Count of entries <= n in A003057.
%C A161680 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
%C A161680 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
%C A161680 a(n-1) is also the number of ordered partitions (compositions) of n >= 1 into exactly 3 parts. - _Juergen Will_, Jan 02 2016
%C A161680 a(n+2) is also the number of weak compositions (ordered weak partitions) of n into exactly 3 parts. - _Juergen Will_, Jan 19 2016
%C A161680 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
%C A161680 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
%C A161680 The lexicographically earliest infinite sequence of nonnegative integers with monotonically increasing differences (that are also nonnegative integers). - _Joe B. Stephen_, Jul 22 2023
%H A161680 Vincenzo Librandi, <a href="/A161680/b161680.txt">Table of n, a(n) for n = 0..10000</a>
%H A161680 Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 4.
%H A161680 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016.
%H A161680 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A161680 Steve Lawford and Yll Mehmeti, <a href="https://arxiv.org/abs/1806.05866">Cliques and a new measure of clustering: with application to U.S. domestic airlines</a>, arXiv:1806.05866 [cs.SI], 2018.
%H A161680 P. A. MacMahon, <a href="http://www.jstor.org/stable/90632">Memoir on the Theory of the Compositions of Numbers</a>, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.
%H A161680 Dennis Walsh, <a href="https://web.archive.org/web/20111208160622/http://frank.mtsu.edu/~dwalsh/NOCONSC3.pdf">Notes on size-2 subsets of [n] that contain no consecutive integers</a>
%H A161680 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Composition.html">Composition</a>
%H A161680 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F A161680 a(n) = (n^2 - n)/2 = n*(n - 1)/2.
%F A161680 a(n) = A000124(n-1)-1 = A000217(n-1).
%F A161680 a(n) = a(n-1)+n-1 (with a(0)=a(1)=0). - _Vincenzo Librandi_, Nov 30 2010
%F A161680 Compositions: C(n,3) = binomial(n-1,n-3) = binomial(n-1,2), n>0. - _Juergen Will_, Jan 02 2015
%F A161680 G.f.: x^2/(1-x)^3. - _Dennis P. Walsh_, Mar 30 2011
%F A161680 G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1-x))^3. - _Juergen Will_, Jan 02 2015
%F A161680 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
%F A161680 a(n) = A244049(n+1) + A004125(n+1). - _Omar E. Pol_, Mar 25 2021
%F A161680 a(n) = A000290(n+1) - A034856(n+1). - _Omar E. Pol_, Mar 30 2021
%F A161680 E.g.f.: exp(x)*x^2/2. - _Stefano Spezia_, Dec 19 2021
%e A161680 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.
%e A161680 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}.
%p A161680 seq(binomial(n,2),n=0..50);
%t A161680 Join[{a = 0}, Table[a += n, {n, 0, 100}]] (* _Vladimir Joseph Stephan Orlovsky_, Jun 12 2011 *)
%t A161680 f[n_] := n(n-1)/2; Array[f, 54, 0] (* _Robert G. Wilson v_, Jul 26 2015 *)
%t A161680 Binomial[Range[0,60],2] (* or *) LinearRecurrence[{3,-3,1},{0,0,1},60] (* _Harvey P. Dale_, Apr 14 2017 *)
%o A161680 (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
%o A161680 (PARI) a(n)=n*(n-1)/2 \\ _Charles R Greathouse IV_, Jun 17 2017
%Y A161680 Cf. A000124, A000217, A000290, A004125, A034856, A244049.
%K A161680 nonn,easy
%O A161680 0,4
%A A161680 _Jaroslav Krizek_, Jun 16 2009
%E A161680 Definition rephrased, offset set to 0 by _R. J. Mathar_, Aug 03 2010