A105599 -id:A105599 - cp's OEIS frontend

A240681 Number of forests with n labeled nodes and 4 trees.

1, 10, 105, 1295, 18865, 320544, 6258000, 138437310, 3428282880, 94059655690, 2833936641536, 93055995703125, 3308477732618240, 126642365068676240, 5193315990469140480, 227160198500847385884, 10557603840000000000000, 519578655591970045435770

Offset: 4

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..200

Column m=4 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 4):
seq(a(n), n=4..30);

Table[n^(n-8) * (n-3)*(n-2)*(n-1)*(n^3 + 21*n^2 + 202*n + 840)/48,{n,4,20}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-8) * (n-3)*(n-2)*(n-1)*(n^3 + 21*n^2 + 202*n + 840)/48. - Vaclav Kotesovec, Sep 06 2014

A240682 Number of forests with n labeled nodes and 5 trees.

Original entry on oeis.org

1, 15, 210, 3220, 55755, 1092105, 24048255, 590412240, 16027796070, 477411574640, 15495339234375, 544652100894720, 20619226977792170, 836670560604157440, 36232055577668433690, 1668081561600000000000, 81363801140161673297535, 4191692026268767965880320

Offset: 5

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..200

Column m=5 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 5):
seq(a(n), n=5..30);

Table[n^(n-10) * (n-4)*(n-3)*(n-2)*(n-1)*(n^4 + 30*n^3 + 451*n^2 + 3846*n + 15120)/384,{n,5,20}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-10) * (n-4)*(n-3)*(n-2)*(n-1)*(n^4 + 30*n^3 + 451*n^2 + 3846*n + 15120)/384. - Vaclav Kotesovec, Sep 06 2014

A240683 Number of forests with n labeled nodes and 6 trees.

Original entry on oeis.org

1, 21, 378, 7056, 143325, 3207897, 79170399, 2146836978, 63641666088, 2051450651250, 71530799628288, 2684845732979592, 107992630908804096, 4636019437800293718, 211623646464000000000, 10237455825414473977524, 523244238837133507448832, 28177157277452320985386539

Offset: 6

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..200

Column m=6 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 6):
seq(a(n), n=6..30);

Table[n^(n-12) * (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^5 + 40*n^4 + 835*n^3 + 10960*n^2 + 87636*n + 332640)/3840,{n,6,25}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-12) * (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^5 + 40*n^4 + 835*n^3 + 10960*n^2 + 87636*n + 332640)/3840. - Vaclav Kotesovec, Sep 06 2014

A240684 Number of forests with n labeled nodes and 7 trees.

Original entry on oeis.org

1, 28, 630, 14070, 331485, 8411634, 231354123, 6899167275, 222569372025, 7741879425280, 289297137120992, 11570476164077376, 493535471267193810, 22376155441920000000, 1074961750207964923710, 54561107576767408522752, 2918071167402563863036269

Offset: 7

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..200

Column m=7 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 7):
seq(a(n), n=7..30);

Table[n^(n-14) * (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^6 + 51*n^5 + 1385*n^4 + 24885*n^3 + 303766*n^2 + 2333976*n + 8648640)/46080,{n,7,25}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-14) * (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^6 + 51*n^5 + 1385*n^4 + 24885*n^3 + 303766*n^2 + 2333976*n + 8648640)/46080. - Vaclav Kotesovec, Sep 06 2014

A240685 Number of forests with n labeled nodes and 8 trees.

Original entry on oeis.org

1, 36, 990, 26070, 705375, 20151846, 614506893, 20073049425, 702495121185, 26300384653400, 1050925859466912, 44702294310795888, 2018603140944000000, 96508616036970572820, 4872478522317533107200, 259140537891648535707618, 14485018396686799073181696

Offset: 8

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 8..200

Column m=8 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 8):
seq(a(n), n=8..30);

Table[n^(n-16) * (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^7 + 63*n^6 + 2135*n^5 + 49245*n^4 + 816256*n^3 + 9527868*n^2 + 71254800*n + 259459200)/645120,{n,8,25}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-16) * (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^7 + 63*n^6 + 2135*n^5 + 49245*n^4 + 816256*n^3 + 9527868*n^2 + 71254800*n + 259459200)/645120. - Vaclav Kotesovec, Sep 06 2014

A240686 Number of forests with n labeled nodes and 9 trees.

Original entry on oeis.org

1, 45, 1485, 45540, 1402830, 44837793, 1508782275, 53789959080, 2036262886515, 81857181636945, 3490649483399793, 157637380245930000, 7524305274666328785, 378816067488484478160, 20074256751067210380645, 1117410784286881766178816, 65207052558569641113281250

Offset: 9

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 9..200

Column m=9 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 9):
seq(a(n), n=9..30);

Table[n^(n-18) * (n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^8 + 76*n^7 + 3122*n^6 + 88760*n^5 + 1873921*n^4 + 29555596*n^3 + 334746252*n^2 + 2455095600*n + 8821612800)/10321920,{n,9,30}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-18) * (n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^8 + 76*n^7 + 3122*n^6 + 88760*n^5 + 1873921*n^4 + 29555596*n^3 + 334746252*n^2 + 2455095600*n + 8821612800)/10321920. - Vaclav Kotesovec, Sep 06 2014

A240687 Number of forests with n labeled nodes and 10 trees.

Original entry on oeis.org

1, 55, 2145, 75790, 2637635, 93783690, 3467403940, 134463763720, 5491244257785, 236503301350745, 10742799174110575, 514243815022230930, 25908948794088640280, 1371861202568610407885, 76216658109172817448960, 4435598473883166992187500, 269963484584876515488140800

Offset: 10

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 10..200

Column m=10 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 10):
seq(a(n), n=10..30);

Table[n^(n-20) * (n-9)*(n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^9 + 90*n^8 + 4386*n^7 + 149436*n^6 + 3859401*n^5 + 77149170*n^4 + 1176873076*n^3 + 13044397176*n^2 + 94273812000*n + 335221286400)/185794560,{n,10,30}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-20) * (n-9)*(n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(n^9 + 90*n^8 + 4386*n^7 + 149436*n^6 + 3859401*n^5 + 77149170*n^4 + 1176873076*n^3 + 13044397176*n^2 + 94273812000*n + 335221286400)/185794560. - Vaclav Kotesovec, Sep 06 2014

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

Original entry on oeis.org

0, 2, 0, 9, 0, 0, 64, 12, 0, 0, 625, 180, 0, 0, 0, 7776, 2730, 120, 0, 0, 0, 117649, 46410, 3780, 0, 0, 0, 0, 2097152, 893816, 99120, 1680, 0, 0, 0, 0, 43046721, 19389384, 2600640, 90720, 0, 0, 0, 0, 0, 1000000000, 469532790, 71734320, 3654000, 30240, 0

Offset: 1

Washington Bomfim, Apr 21 2005

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.

Also the Bell transform of A055860. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			a(8) = 12 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. Two trees on 2 vertices can be labeled in binomial(4,2) ways and to each one of the 2*binomial(4,2) = 12 possibilities there are more 2 possible trees of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide 2*binomial(4,2)*2 by 2!.
Triangle T(n,k) begins:
:       0;
:       2,      0;
:       9,      0,     0;
:      64,     12,     0,    0;
:     625,    180,     0,    0, 0;
:    7776,   2730,   120,    0, 0, 0;
:  117649,  46410,  3780,    0, 0, 0, 0;
: 2097152, 893816, 99120, 1680, 0, 0, 0, 0;

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

Cf. A033185, A055860, A105599, A354794, A360193.

Row sums give A105785.

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^n), 9); # Peter Luschny, Jan 27 2016
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
       binomial(n-1, j-1)*j^(j-1)*x*b(n-j), j=2..n)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 13 2017

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^n]], rows];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2 + ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-1)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).
From Mélika Tebni, Apr 23 2023: (Start)
E.g.f. of column k: (-x - LambertW(-x))^k / k!, k > 0.
Sum_{k=1..n} (-1)^(n-k)*T(n+k,k) = n+1.
Sum_{k=1..n} (-1)^(k+1)*T(n,k) = A360193(n), for n > 0.
Sum_{k=1..n} (-1)^(k+1)*T(n+k,k)/(n+k-1) = 1/n, for n > 1.
T(n,k) = Sum_{j=k..n} j!*abs(Stirling1(j-k,k))*A354794(n,j)/(j-k)!. (End)

A105786 Triangle of the numbers of different forests of m unrooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Original entry on oeis.org

0, 1, 0, 3, 0, 0, 16, 3, 0, 0, 125, 30, 0, 0, 0, 1296, 330, 15, 0, 0, 0, 16807, 4305, 315, 0, 0, 0, 0, 262144, 66248, 5880, 105, 0, 0, 0, 0, 4782969, 1183644, 115290, 3780, 0, 0, 0, 0, 0, 100000000, 24170310, 2467080, 107100, 945, 0, 0, 0, 0, 0, 2357947691, 556409535

Offset: 1

Washington Bomfim, Apr 21 2005

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.

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

			a(8) = 3 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. The unique tree on 2 vertices can be labeled in binomial(4,2) ways and to each one of the binomial(4,2) = 6 possibilities there is just another tree of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide binomial(4,2) by 2!.

Cf. A033185, A105599.

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^(n-1)), 9); # Peter Luschny, Jan 27 2016

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^(n-1)]], rows = 12];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2+ ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-2)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).

A106834 Triangle read by rows: T(n, m) = number of painted forests on labeled vertex set [n] with m trees. Also number of painted forests with exactly n - m edges.

Original entry on oeis.org

1, 1, 2, 3, 6, 3, 16, 30, 18, 4, 125, 220, 135, 40, 5, 1296, 2160, 1305, 420, 75, 6, 16807, 26754, 15750, 5180, 1050, 126, 7, 262144, 401408, 229824, 75460, 16100, 2268, 196, 8, 4782969, 7085880, 3949722, 1282176, 278775, 42336, 4410, 288, 9

Offset: 1

Washington Bomfim, May 19 2005

Row sums equal A101313 (Number of painted forests - exactly one of its trees is painted - on labeled vertex set [n].).

			T(4,3) = 18 because there are 18 such forests with 4 nodes and 3 trees. (See the illustration of this sequence).
Triangle begins:
1;
1,         2;
3,         6,     3;
16,       30,    18,    4;
125,     220,   135,   40,    5;
1296,   2160,  1305,  420,   75,   6;
16807, 26754, 15750, 5180, 1050, 126,  7;

Alois P. Heinz, Rows n = 1..141, flattened
Washington Bomfim, Illustration Of This Sequence. [Broken link?]

Cf. A101313, A105599, A106240.

f:= 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) *f(n-j,m-1), j=1..n-m+1)
      fi
    end:
T:= (n,m)-> m*f(n,m):
seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008

f[n_, m_] := f[n, m] = Which[n<0, 0, n == m, 1, m<1 || m>n, 0, True, Sum[ Binomial[n-1, j-1]*j^(j-2)*f[n-j, m-1], {j, 1, n-m+1}]]; T[n_, m_] := m*f[n, m]; Table[Table[T[n, m], {m, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)

T(n, m)= m * f(n, m), where f(n, m) = number of forests with n nodes and m labeled trees, A105599.

E.g.f.: y*B(x)*exp(y*B(x)), where B(x) is e.g.f. for A000272. - Vladeta Jovovic, May 24 2005

cp's OEIS Frontend

A240681 Number of forests with n labeled nodes and 4 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240682 Number of forests with n labeled nodes and 5 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240683 Number of forests with n labeled nodes and 6 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240684 Number of forests with n labeled nodes and 7 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240685 Number of forests with n labeled nodes and 8 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240686 Number of forests with n labeled nodes and 9 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240687 Number of forests with n labeled nodes and 10 trees.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs