login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1). 6
1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 2, 4, 6, 6, 1, 1, 2, 4, 7, 11, 11, 1, 1, 2, 4, 8, 14, 23, 23, 1, 1, 2, 4, 8, 15, 29, 46, 47, 1, 1, 2, 4, 8, 16, 32, 60, 99, 106, 1, 1, 2, 4, 8, 16, 33, 66, 128, 216, 235, 1, 1, 2, 4, 8, 16, 34, 69, 143, 284, 488, 551, 1, 1, 2, 4, 8, 16, 34, 70, 149, 315, 636, 1121, 1301 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,9

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.

LINKS

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

FORMULA

G.f.: Product_{k>=1} 1/(1 - y^(k-1)*x^k)^A000055(k). - Geoffrey Critzer, Nov 10 2014

EXAMPLE

Triangle begins:

1

1,1

1,1,1

1,1,2,2

1,1,2,3,3

1,1,2,4,6,6 <- T(6,3) = 4 forests on 6 nodes with 3 edges.

1,1,2,4,7,11,11

1,1,2,4,8,14,23,23

1,1,2,4,8,15,29,46,47

1,1,2,4,8,16,32,60,99,106

1,1,2,4,8,16,33,66,128,216,235

1,1,2,4,8,16,34,69,143,284,488,551

1,1,2,4,8,16,34,70,149,315,636,1121,1301

1,1,2,4,8,16,34,71,152,330,710,1467,2644,3159

MAPLE

with(numtheory):

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

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

    end:

t:= n-> `if`(n=0, 1, b(n)-(add(b(k)*b(n-k), k=0..n)-

        `if`(irem(n, 2)=0, b(n/2), 0))/2):

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

      `if`(i<1, 0, expand(add(binomial(t(i)+j-1, j)*

       g(n-i*j, i-1)*x^j, j=0..n/i))))

    end:

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

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

MATHEMATICA

b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}])/(n-1)]; t[n_] := If[n == 0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Expand[Sum[Binomial[t[i] + j - 1, j]*g[n - i*j, i-1]*x^j, {j, 0, n/i}]]]]; T[n_] := CoefficientList[g[n, n], x] // Reverse // Most; Table[T[n], {n, 1, 14}] // Flatten (* Jean-Fran├žois Alcover, Apr 16 2014, after Alois P. Heinz *)

CROSSREFS

Row sums give A005195. Rightmost diagonal gives A000055. Cf. A001858, A138464.

Rows converge to A215930. Reflected table is A095133. - Alois P. Heinz, Apr 11 2014

Sequence in context: A066030 A025863 A305825 * A165621 A284321 A004739

Adjacent sequences:  A136602 A136603 A136604 * A136606 A136607 A136608

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, May 09 2008

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 January 16 15:31 EST 2019. Contains 319195 sequences. (Running on oeis4.)