login
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, 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
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
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Mar 27 2013
STATUS
approved