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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001859 Triangular numbers plus quarter-squares: n*(n+1)/2 + floor((n+1)^2/4) (i.e., A000217(n) + A002620(n+1)).
(Formerly M1368 N0531)
12
0, 2, 5, 10, 16, 24, 33, 44, 56, 70, 85, 102, 120, 140, 161, 184, 208, 234, 261, 290, 320, 352, 385, 420, 456, 494, 533, 574, 616, 660, 705, 752, 800, 850, 901, 954, 1008, 1064, 1121, 1180, 1240, 1302, 1365, 1430, 1496, 1564, 1633, 1704, 1776, 1850, 1925 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of series-reduced planted trees with n+7 nodes and 3 internal nodes.

The trees enumerated with 3 internal nodes are of two types. Those with all internal nodes at different heights are enumerated by the triangular numbers. Those with two internal nodes at the same height are enumerated by the quarter squares. - Michael Somos, May 19 2000

Number of pairs (x,y) with x in {0,...,n}, y even in {0,...,2n}, and x < y. - Clark Kimberling, Jul 02 2012

REFERENCES

John Riordan, personal communication.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

D. D. Frey and J. A. Sellers, Jacobsthal Numbers and Alternating Sign Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.3

S. V. Gervacio and H. Maehara, Partial order on a family of k-subsets of a linearly ordered set, Discr. Math., 306 (2006), 413-419.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

J. Riordan, Letter to N. J. A. Sloane, Oct. 1970

S. G. Wagner, An identity for the cycle indices of rooted tree automorphism groups, Elec. J. Combinat., 13 (2006), #R00.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

FORMULA

a(n) = A000217(n)+A002620(n+1).

a(n) = n + floor( (3n^2+1)/4 ).

G.f.: (2*x+x^2)/((1-x)^2*(1-x^2)).

a(n) = a(n-1) + a(n-2) - a(n-3) + 3 = A002378(n) - A002620(n) = A006578(n-1) + A004526(n+1) - Henry Bottomley, Mar 08 2000

a(n) = A006578(-1-n) for all n in Z. - Michael Somos, May 10 2006

From Mitch Harris, Aug 22 2006: (Start)

a(n) = (6n^2 + 8n + 1 - (-1)^n)/8;

a(n) = Sum_{k=0..n} max(k, n-k). (End)

Starting (2, 5, 10, 16, 24, ...), = binomial transform of [2, 3, 2, -1, 2, -4, 8, -16, 32, ...]. - Gary W. Adamson, Nov 30 2007

a(0)=0, a(1)=2, a(2)=5, a(3)=10, a(n) = 2*a(n-1) + 0*a(n-2) - 2*a(n-3) + a(n-4). - Harvey P. Dale, Apr 01 2012

a(n) = 3*n*(n+1)/2 - A006578(n). - Clark Kimberling, Jul 02 2012

a(2*n) = A045944(n), a(2*n - 1) = A049450(n) for all n in Z. - Michael Somos, Nov 03 2014

0 = -6 + a(n) - 2*a(n+2) + a(n+4) for all n in Z. - Michael Somos, Nov 03 2014

0 = a(n)*(+a(n+1) - a(n+2)) + a(n+1)*(-3 - a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Nov 03 2014

a(n) = Sum_{k=1..n} floor((n+k+2)/2). - Wesley Ivan Hurt, Mar 31 2017

EXAMPLE

For n=1 we find 2 planted trees with 8 nodes, 3 of which are internal (i) and 5 are endpoints (e):

.e...e...e...e....e...e....

...i.......i........i...e..

.......i..............i...e

.......e................i..

........................e..

G.f. = 2*x + 5*x^2 + 10*x^3 + 16*x^4 + 24*x^5 + 33*x^6 + 44*x^7 + 56*x^8 + ...

MAPLE

A001859:=(-1-z^2-2*z^3+z^4)/(z+1)/(z-1)^3; # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence with an additional leading 1

with (combinat):seq(count(Partition((3*n+2)), size=3), n=0..50); # Zerinvary Lajos, Mar 28 2008

MATHEMATICA

With[{nn=60}, Total/@Thread[{Accumulate[Range[0, nn]], Floor[Range[ nn+1]^2/4]}]] (* or *) LinearRecurrence[{2, 0, -2, 1}, {0, 2, 5, 10}, 60] (* Harvey P. Dale, Apr 01 2012 *)

PROG

(PARI) {a(n) = n + (3*n^2 + 1) \ 4};

(Haskell)

a001859 n = a000217 n + a002620 (n + 1)  -- Reinhard Zumkeller, Dec 20 2012

CROSSREFS

Cf. A006578, A045944, A049450.

First differences of A045947.

Antidiagonal sums of array A003984.

Cf. A107661, A077043.

Cf. A185212 (odd terms).

Sequence in context: A026056 A267159 A084587 * A011903 A078435 A049815

Adjacent sequences:  A001856 A001857 A001858 * A001860 A001861 A001862

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Entry improved by Michael Somos

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 February 20 06:45 EST 2018. Contains 299358 sequences. (Running on oeis4.)