login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A106235 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices. 1

%I

%S 0,1,0,2,0,0,4,1,0,0,9,2,0,0,0,20,7,1,0,0,0,48,17,2,0,0,0,0,115,48,7,

%T 1,0,0,0,0,286,124,21,2,0,0,0,0,0,719,336,60,7,1,0,0,0,0,0,1842,888,

%U 171,21,2,0,0,0,0,0,0,4766,2393,488,65,7,1,0,0,0,0,0,0

%N Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices.

%C Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree. A033185(n) = A106235(n) + A106234(n).

%H Alois P. Heinz, <a href="/A106235/b106235.txt">Rows n = 1..141, flattened</a>

%F a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and no part equal to 1, of Product_{i=1..N} binomial(A000081(i)+Ki-1, Ki).

%e a(12)=2 because 5 nodes can be partitioned in two trees only in a way: one tree gets 3 nodes and the other tree gets 2. Since A000081(3) = 2 and A000081(2)=1, there are two forests.

%e Triangle T(n,k) begins:

%e 0;

%e 1, 0;

%e 2, 0, 0;

%e 4, 1, 0, 0;

%e 9, 2, 0, 0, 0;

%e 20, 7, 1, 0, 0, 0;

%e 48, 17, 2, 0, 0, 0, 0;

%e 115, 48, 7, 1, 0, 0, 0, 0;

%e 286, 124, 21, 2, 0, 0, 0, 0, 0;

%e 719, 336, 60, 7, 1, 0, 0, 0, 0, 0;

%p with(numtheory):

%p g:= proc(n) option remember; `if`(n<=1, n, (add(add(

%p d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))

%p end:

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1,

%p 0, expand(add(x^j*b(n-i*j, i-1)*

%p binomial(g(i)+j-1, j), j=0..n/i))))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):

%p seq(T(n), n=1..14); # _Alois P. Heinz_, Jun 25 2014

%t g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 1, 0, Expand[Sum[x^j*b[n-i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0, n/i}]]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* _Jean-Fran├žois Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)

%Y Cf. A033185, A106234.

%K nonn,tabl

%O 1,4

%A _Washington Bomfim_, Apr 26 2005

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 12:34 EDT 2020. Contains 337289 sequences. (Running on oeis4.)