|
%I #158 Jan 06 2024 09:20:47
%S 0,0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,
%T 231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,
%U 741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378
%N a(n) = binomial(n,2): number of size-2 subsets of {0,1,...,n} that contain no consecutive integers.
%C Essentially the same as A000217: zero followed by A000217. - _Joerg Arndt_, Jul 26 2015
%C Count of entries <= n in A003057.
%C 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 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 a(n-1) is also the number of ordered partitions (compositions) of n >= 1 into exactly 3 parts. - _Juergen Will_, Jan 02 2016
%C 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 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 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 The lexicographically earliest infinite sequence of nonnegative integers with monotonically increasing differences (that are also nonnegative integers). - _Joe B. Stephen_, Jul 22 2023
%H Vincenzo Librandi, <a href="/A161680/b161680.txt">Table of n, a(n) for n = 0..10000</a>
%H 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 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Composition.html">Composition</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F a(n) = (n^2 - n)/2 = n*(n - 1)/2.
%F a(n) = A000124(n-1)-1 = A000217(n-1).
%F a(n) = a(n-1)+n-1 (with a(0)=a(1)=0). - _Vincenzo Librandi_, Nov 30 2010
%F Compositions: C(n,3) = binomial(n-1,n-3) = binomial(n-1,2), n>0. - _Juergen Will_, Jan 02 2015
%F G.f.: x^2/(1-x)^3. - _Dennis P. Walsh_, Mar 30 2011
%F G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1-x))^3. - _Juergen Will_, Jan 02 2015
%F 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 a(n) = A244049(n+1) + A004125(n+1). - _Omar E. Pol_, Mar 25 2021
%F a(n) = A000290(n+1) - A034856(n+1). - _Omar E. Pol_, Mar 30 2021
%F E.g.f.: exp(x)*x^2/2. - _Stefano Spezia_, Dec 19 2021
%e 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 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 seq(binomial(n,2),n=0..50);
%t Join[{a = 0}, Table[a += n, {n, 0, 100}]] (* _Vladimir Joseph Stephan Orlovsky_, Jun 12 2011 *)
%t f[n_] := n(n-1)/2; Array[f, 54, 0] (* _Robert G. Wilson v_, Jul 26 2015 *)
%t Binomial[Range[0,60],2] (* or *) LinearRecurrence[{3,-3,1},{0,0,1},60] (* _Harvey P. Dale_, Apr 14 2017 *)
%o (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 (PARI) a(n)=n*(n-1)/2 \\ _Charles R Greathouse IV_, Jun 17 2017
%Y Cf. A000124, A000217, A000290, A004125, A034856, A244049.
%K nonn,easy
%O 0,4
%A _Jaroslav Krizek_, Jun 16 2009
%E Definition rephrased, offset set to 0 by _R. J. Mathar_, Aug 03 2010
|
