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
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, 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, 171, 21, 2, 0, 0, 0, 0, 0, 0, 4766, 2393, 488, 65, 7, 1, 0, 0, 0, 0, 0, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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).

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

FORMULA

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).

EXAMPLE

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.

Triangle T(n,k) begins:

    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, 1, 0, 0, 0, 0;

  286, 124, 21, 2, 0, 0, 0, 0, 0;

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

MAPLE

with(numtheory):

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

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

    end:

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

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

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

    end:

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

seq(T(n), n=1..14);  # Alois P. Heinz, Jun 25 2014

MATHEMATICA

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 *)

CROSSREFS

Cf. A033185, A106234.

Sequence in context: A136334 A155039 A238858 * A288098 A118965 A252729

Adjacent sequences:  A106232 A106233 A106234 * A106236 A106237 A106238

KEYWORD

nonn,tabl

AUTHOR

Washington Bomfim, Apr 26 2005

STATUS

approved

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 August 14 07:04 EDT 2020. Contains 336477 sequences. (Running on oeis4.)