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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244372 Number T(n,k) of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows. 14
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 2, 1, 0, 1, 10, 6, 2, 1, 0, 1, 22, 16, 6, 2, 1, 0, 1, 45, 43, 17, 6, 2, 1, 0, 1, 97, 113, 49, 17, 6, 2, 1, 0, 1, 206, 300, 136, 50, 17, 6, 2, 1, 0, 1, 450, 787, 386, 142, 50, 17, 6, 2, 1, 0, 1, 982, 2074, 1081, 409, 143, 50, 17, 6, 2, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,9

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

EXAMPLE

The A000081(5) = 9 rooted trees with 5 nodes sorted by maximal outdegree are:

:  o  :   o     o     o       o     o   :   o     o   :    o    :

:  |  :   |     |    / \     / \   / \  :   |    /|\  :  /( )\  :

:  o  :   o     o   o   o   o   o o   o :   o   o o o : o o o o :

:  |  :   |    / \  |      / \    |   | :  /|\  |     :         :

:  o  :   o   o   o o     o   o   o   o : o o o o     :         :

:  |  :  / \  |     |                   :             :         :

:  o  : o   o o     o                   :             :         :

:  |  :                                 :             :         :

:  o  :                                 :             :         :

:     :                                 :             :         :

: -1- : ---------------2--------------- : -----3----- : ---4--- :

Thus row 5 = [0, 1, 5, 2, 1].

Triangle T(n,k) begins:

1;

0,  1;

0,  1,   1;

0,  1,   2,    1;

0,  1,   5,    2,    1;

0,  1,  10,    6,    2,   1;

0,  1,  22,   16,    6,   2,   1;

0,  1,  45,   43,   17,   6,   2,  1;

0,  1,  97,  113,   49,  17,   6,  2,  1;

0,  1, 206,  300,  136,  50,  17,  6,  2,  1;

0,  1, 450,  787,  386, 142,  50, 17,  6,  2,  1;

0,  1, 982, 2074, 1081, 409, 143, 50, 17,  6,  2,  1;

MAPLE

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,

      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*

       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))

    end:

T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):

seq(seq(T(n, k), k=0..n-1), n=1..14);

MATHEMATICA

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-Fran├žois Alcover, Jul 01 2014, translated from Maple *)

CROSSREFS

Column k=2-10 give: A244398, A244399, A244400, A244401, A244402, A244403, A244404, A244405, A244406.

T(2n,n) gives A244407(n).

T(2n+1,n) gives A244410(n).

Row sum give A000081.

Cf. A244454.

Sequence in context: A220235 A066603 A263339 * A119331 A239145 A151824

Adjacent sequences:  A244369 A244370 A244371 * A244373 A244374 A244375

KEYWORD

nonn,tabl

AUTHOR

Joerg Arndt and Alois P. Heinz, Jun 26 2014

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 March 27 22:02 EDT 2017. Contains 284182 sequences.