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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n. 38
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

REFERENCES

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

N. J. A. Sloane, Transforms

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Index entries for sequences related to rooted trees

FORMULA

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.

G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014

Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

EXAMPLE

From Joerg Arndt, Aug 18 2014: (Start)

Triangle starts:

01: 1

02: 1    0

03: 1    1    0

04: 1    2    1    0

05: 1    4    3    1    0

06: 1    6    8    4    1    0

07: 1    9   18   14    5    1    0

08: 1   12   35   39   21    6    1    0

09: 1   16   62   97   72   30    7    1    0

10: 1   20  103  212  214  120   40    8    1    0

11: 1   25  161  429  563  416  185   52    9    1    0

12: 1   30  241  804 1344 1268  732  270   65   10    1    0

13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0

...

The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:

:

:     1:  [ 0 1 2 3 4 ]   1

:  O--o--o--o--o

:

:     2:  [ 0 1 2 3 3 ]   2

:  O--o--o--o

:        .--o

:

:     3:  [ 0 1 2 3 2 ]   2

:  O--o--o--o

:     .--o

:

:     4:  [ 0 1 2 3 1 ]   2

:  O--o--o--o

:  .--o

:

:     5:  [ 0 1 2 2 2 ]   3

:  O--o--o

:     .--o

:     .--o

:

:     6:  [ 0 1 2 2 1 ]   3

:  O--o--o

:     .--o

:  .--o

:

:     7:  [ 0 1 2 1 2 ]   2

:  O--o--o

:  .--o--o

:

:     8:  [ 0 1 2 1 1 ]   3

:  O--o--o

:  .--o

:  .--o

:

:     9:  [ 0 1 1 1 1 ]   4

:  O--o

:  .--o

:  .--o

:  .--o

:

This gives [1, 4, 3, 1, 0], row n=5 of the triangle.

(End)

G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

MATHEMATICA

rut[n_]:=rut[n]=If[n===1, {{}}, Join@@Function[c, Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];

Table[Length[Select[rut[n], Count[#, {}, {-2}]===k&]], {n, 13}, {k, n}] (* Gus Wiseman, Mar 19 2018 *)

PROG

(PARI) {T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

CROSSREFS

Row sums give A000081.

Columns 2 through 12: A002620(n-1), A055278-A055287.

Cf. A055288, A055289, A055290.

Cf. A000081, A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

Sequence in context: A127709 A128307 A034369 * A301422 A055340 A058716

Adjacent sequences:  A055274 A055275 A055276 * A055278 A055279 A055280

KEYWORD

nonn,tabl,eigen

AUTHOR

Christian G. Bower, May 09 2000

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 16:08 EST 2019. Contains 319307 sequences. (Running on oeis4.)