A005199 -id:A005199

Search: a005199 -id:a005199

Displaying 1-1 of 1 result found.

page 1

A336087

Triangle read by rows: T(n, k) is the number of forests with n (unlabeled) nodes and k planted trees.

+10
2

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 1, 0, 0, 0, 9, 3, 1, 0, 0, 0, 20, 6, 1, 0, 0, 0, 0, 48, 16, 3, 1, 0, 0, 0, 0, 115, 37, 7, 1, 0, 0, 0, 0, 0, 286, 96, 18, 3, 1, 0, 0, 0, 0, 0, 719, 239, 44, 7, 1, 0, 0, 0, 0, 0, 0, 1842, 622, 117, 19, 3, 1, 0, 0, 0, 0, 0, 0, 4766, 1607, 299, 46, 7, 1, 0, 0, 0, 0, 0, 0, 0, 12486, 4235, 793, 124

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,7

COMMENTS

The number of planted trees with n+1 nodes is equal to the number of rooted trees with n nodes. [See Palmer-Schwenk link, pp. 115].

LINKS

Table of n, a(n) for n=1..95.

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

Index entries for sequences related to rooted trees

FORMULA

T(1,1) = 0, if n >= 2 T(n,k) = Sum_{P_1(n,k)}( Product_{j=2..n} binomial(A000081(j-1) + c_j - 1, c_j) ), where P_1(n, k) is the set of the partitions of n with k parts greater than one: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0.

If k > floor(n/2), T(n,k) = 0; otherwise T(n,k) = A033185(n-k, k).

EXAMPLE

Triangle T(n,k)

n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 0;

2 1, 0;

3 1, 0, 0;

4 2, 1, 0, 0;

5 4, 1, 0, 0, 0;

6 9, 3, 1, 0, 0, 0;

7 20, 6, 1, 0, 0, 0, 0;

8 48, 16, 3, 1, 0, 0, 0, 0;

9 115, 37, 7, 1, 0, 0, 0, 0, 0;

10 286, 96, 18, 3, 1, 0, 0, 0, 0, 0;

11 719, 239, 44, 7, 1, 0, 0, 0, 0, 0, 0;

12 1842, 622, 117, 19, 3, 1, 0, 0, 0, 0, 0, 0;

13 4766, 1607, 299, 46, 7, 1, 0, 0, 0, 0, 0, 0, 0;

14 12486, 4235, 793, 124, 19, 3, 1, 0, 0, 0, 0, 0, 0, 0;

15 32973, 11185, 2095, 320, 47, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0;

...

n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

A005199(6) = Sum_{k=1..6}( k * T(6,k) ) = 1*9 + 2*3 +3*1 = 18.

PROG

(PARI) g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;

for(j=1, m, f[j+1]=1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1])); f[m+1] };

global(max_n = 130); A000081 = vector(max_n, n, g(n-1));

F(n, t)={my(s=0, D, c, P_1); if(n==1, return(0)); forpart(P_1 = n, D = Set(P_1); c = vector(#D); for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));

s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k])), [2, n], [t, t]); s};

CROSSREFS

Cf. A000081, A005199, A005198 (row sums), A033185.

KEYWORD

nonn,tabl

AUTHOR

Washington Bomfim, Jul 08 2020

STATUS

approved

page 1

Search completed in 0.011 seconds