|
| |
|
|
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)
|
|
8
| |
|
|
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; 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
|
|
|
REFERENCES
| 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.
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. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
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 to sequences with linear recurrences with constant coefficients, signature (2,0,-2,1).
|
|
|
FORMULA
| a(n) = A000217(n)+A002620(n+1).
a(n) = n+[ (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 (se16(AT)btinternet.com), Mar 08 2000
a(-1-n)=A006578(n). - Michael Somos May 10 2006
a(n) = (6n^2 + 8n + 1 - (-1)^n)/8 a(n) = Sum[Max[k, n-k], {k,0,n}] - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Aug 22 2006
Starting (2, 5, 10, 16, 24,...), = binomial transform of [2, 3, 2, -1, 2, -4, 8, -16, 32,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 30 2007
|
|
|
EXAMPLE
| For n=1 we find 2 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..
|
|
|
MAPLE
| A001859:=(-1-z**2-2*z**3+z**4)/(z+1)/(z-1)**3; [Conjectured by S. 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 (zerinvarylajos(AT)yahoo.com), Mar 28 2008
|
|
|
PROG
| (PARI) a(n)=n+(3*n^2+1)\4
|
|
|
CROSSREFS
| A045944(n)=A001859(2n), A049450(n)=A001859(2n-1).
First differences of A045947.
Antidiagonal sums of array A003984.
Cf. A107661, A006578, A077043.
Sequence in context: A031871 A026056 A084587 * A011903 A078435 A049815
Adjacent sequences: A001856 A001857 A001858 * A001860 A001861 A001862
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Entry improved by Michael Somos
|
| |
|
|
