A218666 Triangular array read by rows: T(n,k) is the number of unlabeled rooted trees with n nodes in which the largest subtree (of the root) has exactly k nodes; n>=2, 1<=k<=n-1.

1, 1, 1, 1, 1, 2, 1, 2, 2, 4, 1, 2, 4, 4, 9, 1, 3, 7, 8, 9, 20, 1, 3, 9, 16, 18, 20, 48, 1, 4, 12, 30, 36, 40, 48, 115, 1, 4, 18, 38, 81, 80, 96, 115, 286, 1, 5, 21, 64, 144, 180, 192, 230, 286, 719, 1, 5, 27, 92, 216, 400, 432, 460, 572, 719, 1842

Offset

2,6

Comments

Row sums are A000081.

Diagonal terms (i.e., T(n,n-1)) are A000081(n-1).

Links

Alois P. Heinz, Rows n = 2..142, flattened

Formula

O.g.f. for column k: A_k(x) - A_{k-1}(x) with

A_k(x) = x*Product_{j=1..k} 1/(1 - x^j)^A000081(j).

Example

....o..........o..........o..........o....
....|..........|........./ \......../|\...
....o..........o........o   o......o o o..
....|........./ \.......|    .............
....o........o   o......o    .............
....|.....................................
....o.....................................
T(4,3) = 2 because the 2 leftmost graphs have 3 nodes in the largest subtree.  T(4,2) = T(4,1) = 1 as seen in the two rightmost graphs.
1,
1, 1;
1, 1,  2;
1, 2,  2,  4;
1, 2,  4,  4,  9;
1, 3,  7,  8,  9, 20;
1, 3,  9, 16, 18, 20, 48;
1, 4, 12, 30, 36, 40, 48, 115;
1, 4, 18, 38, 81, 80, 96, 115, 286;

Maple

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..n/i))) end:
h:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=1..n/i))) end:
T:= (n, k)-> h(n-1, k):
seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Mar 27 2013

Mathematica

nn=10; f[list_]:=Select[list, #>0&]; t[x_]:=Sum[a[n]x^n, {n, 0, nn}]; b=Level[Table[sol=SolveAlways[0==Series[t[x]-x Product[1/(1-x^i)^a[i], {i, 1, n}], {x, 0, nn}], x]; Table[a[n], {n, 0, nn}]/.sol, {n, 0, nn}], {2}]; Map[f, Drop[Transpose[Table[b[[k+1]]-b[[k]], {k, 1, nn}]], 2]]//Grid

Crossrefs

Sequence in context: A366600 A365461 A131097 * A062790 A046640 A347101

Adjacent sequences: A218663 A218664 A218665 * A218667 A218668 A218669

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 27 2013

Status

approved