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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes. 22
1, 1, 1, 3, 3, 1, 16, 15, 6, 1, 125, 110, 45, 10, 1, 1296, 1080, 435, 105, 15, 1, 16807, 13377, 5250, 1295, 210, 21, 1, 262144, 200704, 76608, 18865, 3220, 378, 28, 1, 4782969, 3542940, 1316574, 320544, 55755, 7056, 630, 36, 1, 100000000, 72000000, 26100000, 6258000, 1092105, 143325, 14070, 990, 45, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Row sums equal A001858 (number of forests of labeled trees with n nodes).

Also the Bell transform of A000272(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

The permutohedron (convex hull of permutations on 1,...,n in R^n) has Ehrhart polynomial Sum_{k=0..n-1} T(n,n-k) t^k. - Matthieu Josuat-Vergès, Mar 31 2018

REFERENCES

B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)

LINKS

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

Washington Bomfim, Illustration Of This Sequence.

Mathoverflow, Is there a formula for the number of labeled forests with k components on n vertices?

FORMULA

T(n,m) = Sum_{k=1..n-m+1} binomial(n-1,k-1)*k^(k-2)*T(n-k,m-1), T(n,0) = 0 if n>0, T(0,0) = 1. - Vladeta Jovovic and Washington Bomfim.

The value of T(n, m) can be calculated by the formula in Bollobas, pp. 172, exercise 44. Also T(n, m)= sum N/D over the partitions of n, 1*K(1) + 2*K(2) + ... + n*K(n), with exactly m parts, where N = n! * product_{i = 1..n} i^( (i-2) * K(i) ) and D = product_{i = 1..n} ( K(i)! * (i!)^K(i) ).

From Peter Bala, Aug 14 2012: (Start)

E.g.f.: A(x,t) := exp(t*F(x)) = 1 + t*x + (t + t^2)*x^2/2! + (3*t + 3*t^2 + t^3)*x^3/3! + ..., where F(x) = sum {n >= 1} n^(n-2)*x^n/n! is the e.g.f. for labeled trees (see A000272). The row polynomials R(n,t) are thus a sequence of binomial type polynomials.

Differentiating A(x,t) w.r.t. x yields A'(x,t) = t*A(x,t)*F'(x) leading to the recurrence equation for the row polynomials R(n,t) = t*sum {k = 0..n-1} (k+1)^(k-1)*binomial(n-1,k)*R(n-k-1,t) with R(0,t) = 1 and R(1,t) = t: the above recurrence for the table entries follows from this.

(End)

T(n,m) = (1/m!) * SUM_{j=0..m} (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)!. Due to A. Renyi. - Max Alekseyev, Oct 08 2014

EXAMPLE

T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.

Triangle begins:

      1;

      1,     1;

      3,     3,    1;

     16,    15,    6,    1;

    125,   110,   45,   10,   1;

   1296,  1080,  435,  105,  15,  1;

  16807, 13377, 5250, 1295, 210, 21, 1;

MAPLE

T:= proc(n, m) option remember;

      if n<0 then 0

    elif n=m then 1

    elif m<1 or m>n then 0

    else add(binomial(n-1, j-1)*j^(j-2)*T(n-j, m-1), j=1..n-m+1)

      fi

    end:

seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008

# The function BellMatrix is defined in A264428.

# Adds (1, 0, 0, 0, ..) as column 0.

BellMatrix(n -> (n+1)^(n-1), 9); # Peter Luschny, Jan 27 2016

MATHEMATICA

f[list_]:=Select[list, #>0&]; Flatten[Map[f, Transpose[Table[t = Sum[n^(n - 2) x^n/n!, {n, 1, 20}]; Drop[Range[0, 8]! CoefficientList[Series[t^k/k!, {x, 0, 8}], x], 1], {k, 1, 8}]]]] (* Geoffrey Critzer, Nov 22 2011 *)

T[n_, m_] := Sum[(-1/2)^j*Binomial[m, j]*Binomial[n-1, m+j-1]*n^(n-m-j)*(m + j)!, {j, 0, m}]/m!; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 09 2016, after Max Alekseyev *)

rows = 10;

t = Table[(n+1)^(n-1), {n, 0, rows}];

T[n_, k_] := BellY[n, k, t];

Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

PROG

(PARI) { T(n, m) = sum(j=0, m, (-1/2)^j * binomial(m, j) * binomial(n-1, m+j-1) * n^(n-m-j)* (m+j)! )/m! } /* Max Alekseyev, Oct 08 2014 */

(GAP) Flat(List([1..11], n->List([1..n], m->(1/Factorial(m)*Sum([0..m], j->(-1/2)^j*Binomial(m, j)*Binomial(n-1, m+j-1)*n^(n-m-j)*Factorial(m+j)))))); # Muniru A Asiru, Apr 01 2018

CROSSREFS

Cf. A033185, A106240.

Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008

Columns k=1-10 give: A000272, A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687.

T(2n,n) gives A302112.

Sequence in context: A112292 A001497 A123244 * A239895 A106210 A033842

Adjacent sequences:  A105596 A105597 A105598 * A105600 A105601 A105602

KEYWORD

nonn,tabl

AUTHOR

Washington Bomfim, Apr 14 2005; revised May 19 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 10:07 EST 2018. Contains 317275 sequences. (Running on oeis4.)