login
The OEIS is supported by the many generous donors 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
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
Row sums give A000081.
Cf. A001678, A244372, A244530 (ordered unlabeled rooted trees).
Sequence in context: A262964 A135481 A180049 * A238123 A128311 A334076
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)