A179438 Triangle T(n,k) read by rows: number of forests of rooted trees whose trees have sizes given by the k-th partition of n listed in Abramowitz and Stegun order, 1 <= k <= A000041(n).

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 1, 9, 4, 2, 2, 1, 1, 1, 20, 9, 4, 3, 4, 2, 1, 2, 1, 1, 1, 48, 20, 9, 8, 9, 4, 3, 2, 4, 2, 1, 2, 1, 1, 1, 115, 48, 20, 18, 10, 20, 9, 8, 4, 3, 9, 4, 3, 2, 1, 4, 2, 1, 2, 1, 1, 1, 286, 115, 48, 40, 36, 48, 20, 18, 10, 9, 8, 4, 20, 9, 8, 4, 3, 2, 9, 4, 3, 2, 1, 4, 2, 1, 2, 1, 1, 1

Offset

0,5

Comments

Forests of rooted trees with n nodes and k trees correspond with rooted trees with n + 1 nodes and k subtrees.

This triangle is a refinement of the triangle A033185.

When all the parts of a partition are unequal, values can be calculated using simple multiplication.

In the more general case, parts of size s and multiplicity m give rise to rooted trees in binomial(m + A000081(s) - 1, m) ways. - Andrew Howroyd, Oct 04 2025

References

N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736-1936, Clarendon Press, 1976, pages 40-43.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2713 (rows 0..20)

Example

Triangle begins:
  0 | 1;
  1 | 1;
  2 | 1, 1;
  3 | 2, 1, 1;
  4 | 4, 2, 1, 1, 1;
  5 | 9, 4, 2, 2, 1, 1, 1;
  6 | 20, 9, 4, 3, 4, 2, 1, 2, 1, 1, 1;
  7 | 48, 20, 9, 8, 9, 4, 3, 2, 4, 2, 1, 2, 1, 1, 1;
  ...
T(6,4) = 3 corresponds to the partition {3,3}. There are two different trees of size 3 so there are 3 choices.

Prog

(PARI)
TreeSeq(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); A}
C(sig, q)={my(S=Set(sig)); prod(k=1, #S, my(c=#select(t->t==S[k], sig)); binomial(c+q[S[k]]-1, c)) }
Row(n)=my(q=TreeSeq(n)); [C(Vec(p), q) | p<-partitions(n)]
{ for(n=0, 7, print(Row(n))) } \\ Andrew Howroyd, Oct 03 2025

Crossrefs

Cf. A000041 (row lengths), A000081 (row sums), A033185, A036036.

Sequence in context: A365582 A367559 A099020 * A389136 A211970 A089688

Adjacent sequences: A179435 A179436 A179437 * A179439 A179440 A179441

Keyword

nonn,look,tabf

Author

Alford Arnold, Jul 14 2010

Extensions

Edited, a(0)=1 prepended and a(23) onwards from Andrew Howroyd, Oct 03 2025

Status

approved