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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244454 Number T(n,k) of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows. 13
1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 7, 1, 0, 1, 0, 17, 2, 0, 0, 1, 0, 42, 4, 1, 0, 0, 1, 0, 105, 7, 2, 0, 0, 0, 1, 0, 267, 15, 2, 1, 0, 0, 0, 1, 0, 684, 28, 4, 2, 0, 0, 0, 0, 1, 0, 1775, 56, 7, 2, 1, 0, 0, 0, 0, 1, 0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

T(1,0) = 1 by convention.

Sum_{i=2..n-1} T(n,i) = A001678(n+1) for n>1.

LINKS

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

EXAMPLE

The A000081(5) = 9 rooted trees with 5 nodes sorted by minimal outdegree of inner nodes 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--- : ---4--- :

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

Triangle T(n,k) begins:

1;

0,    1;

0,    1,   1;

0,    3,   0,  1;

0,    7,   1,  0, 1;

0,   17,   2,  0, 0, 1;

0,   42,   4,  1, 0, 0, 1;

0,  105,   7,  2, 0, 0, 0, 1;

0,  267,  15,  2, 1, 0, 0, 0, 1;

0,  684,  28,  4, 2, 0, 0, 0, 0, 1;

0, 1775,  56,  7, 2, 1, 0, 0, 0, 0, 1;

0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1;

MAPLE

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

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

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

    end:

T:= (n, k)-> b(n-1$2, k$2) -`if`(n=1 and 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, If[t == 0 || t == k, 1, 0], If[i<1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]* b[n-i*j, i-1, Max[0, t-j], k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[n == 1 && 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, Jan 08 2015, translated from Maple *)

CROSSREFS

Columns k=0-10 give: A000007(n-1), A244455, A244456, A244457, A244458, A244459, A244460, A244461, A244462, A244463, A244464.

Row sums give A000081.

Cf. A001678, A244372, A244530 (ordered unlabeled rooted trees).

Sequence in context: A262964 A135481 A180049 * A238123 A128311 A132884

Adjacent sequences:  A244451 A244452 A244453 * A244455 A244456 A244457

KEYWORD

nonn,tabl

AUTHOR

Joerg Arndt and Alois P. Heinz, Jun 28 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 April 27 00:46 EDT 2017. Contains 285506 sequences.