

A161680


a(n) = binomial(n,2): number of size2 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 size2 subsets of [n+1] that contain no consecutive integers, a(n+1) is the nth triangular number.  Dennis P. Walsh, Mar 30 2011
Construct the nth 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(n1) 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


REFERENCES

HsienKuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wpcontent/files/2016/12/aathhrr1.pdf. Also Exact and Asymptotic Solutions of a DivideandConquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835901.
Dennis Walsh, Notes on size2 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(n1)1 = A000217(n1).
a(n) = a(n1)+n1 (with a(0)=a(1)=0).  Vincenzo Librandi, Nov 30 2010
Compositions: C(n,3) = binomial(n1,n3) = binomial(n1,2), n>0.  Juergen Will, Jan 02 2015
G.f.: x^2/(1x)^3.  Dennis P. Walsh, Mar 30 2011
G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1x))^3.  Juergen Will, Jan 02 2015
a(n1) = 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 size2 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(n1)/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*(n1)))+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*(n1)/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



