A235596 -id:A235596 - cp's OEIS frontend

A133399 Triangle T(n,k)=number of forests of labeled rooted trees with n nodes, containing exactly k trees of height one, all others having height zero (n>=0, 0<=k<=floor(n/2)).

1, 1, 1, 2, 1, 9, 1, 28, 12, 1, 75, 120, 1, 186, 750, 120, 1, 441, 3780, 2100, 1, 1016, 16856, 21840, 1680, 1, 2295, 69552, 176400, 45360, 1, 5110, 272250, 1224720, 705600, 30240, 1, 11253, 1026300, 7692300, 8316000, 1164240, 1, 24564, 3762132, 45018600

Offset: 0

Alois P. Heinz, Nov 24 2007

			Triangle begins:
  1;
  1;
  1,     2;
  1,     9;
  1,    28,     12;
  1,    75,    120;
  1,   186,    750,     120;
  1,   441,   3780,    2100;
  1,  1016,  16856,   21840,   1680;
  1,  2295,  69552,  176400,  45360;
  1,  5110, 272250, 1224720, 705600, 30240;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.

Columns k=1,2 give: A058877, A133386.
Row sums give: A000248.
T(2n,n) = A001813(n), T(2n+1,n) = A002691(n).
Reading the table by diagonals gives triangle A198204. - Peter Bala, Jul 31 2012
Cf. A235596.

/* As triangle */ [[Binomial(n,k)*Factorial(k)*StirlingSecond(n-k+1,k+1): k in [0..Floor(n/2)]]: n in [0.. 15]]; // Vincenzo Librandi, Jun 06 2019

T:= (n,k)-> binomial(n,k)*k!*Stirling2(n-k+1,k+1): for n from 0 to 10 do lprint(seq(T(n, k), k=0..floor(n/2))) od;

nn=12;f[list_]:=Select[list,#>0&];Map[f,Range[0,nn]!CoefficientList[ Series[Exp[y x (Exp[x]-1)] Exp[x],{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 09 2013 *)
t[n_, k_] := Binomial[n, k]*k!*StirlingS2[n-k+1, k+1]; Table[t[n, k], {n, 0, 12}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Dec 19 2013 *)

T(n,k) = C(n,k) * k! * stirling2(n-k+1,k+1).
E.g.f.: exp(y*x*(exp(x)-1))*exp(x). - Geoffrey Critzer, Feb 09 2013
Sum_{k=1..floor(n/2)} T(n,k) = A235596(n+1). - Alois P. Heinz, Jun 21 2019

A235595 Triangle read by rows: the triangle in A034855, with the n-th row normalized by dividing it by n.

Original entry on oeis.org

1, 1, 2, 1, 9, 6, 1, 40, 60, 24, 1, 195, 560, 420, 120, 1, 1056, 5550, 6240, 3240, 720, 1, 6321, 59472, 94710, 68880, 27720, 5040, 1, 41392, 692440, 1527456, 1426320, 792960, 262080, 40320, 1, 293607, 8753040, 26418168, 30560544, 21213360, 9676800, 2721600, 362880, 1, 2237920, 119723130, 490458240, 691331760, 570810240, 323114400, 125798400, 30844800, 3628800

Offset: 2

N. J. A. Sloane, Jan 14 2014

T(n,k) is the number of forests of labeled rooted trees with n nodes and height k Cf. A210725. Equivalently, T(n,k) is the number of nilpotent partial functions on [n] with index k+1. - Geoffrey Critzer, Nov 26 2021

			Triangle begins:
1.
1, 2,
1, 9, 6,
1, 40, 60, 24,
1, 195, 560, 420, 120,
1, 1056, 5550, 6240, 3240, 720,
1, 6321, 59472, 94710, 68880, 27720, 5040,
1, 41392, 692440, 1527456,1426320, 792960, 262080, 40320,
1, 293607, 8753040, 26418168, 30560544, 21213360, 9676800, 2721600, 362880,
...

Alois P. Heinz, Rows n = 2..142, flattened

Cf. A000435, A034855, A001854, A210725, A234953, A235596, A236396.

Row sums give A000272.

b:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*j*b(j-1, h-1)*b(n-j, h), j=1..n))
    end:
T:= (n,k)-> b(n-1, k-1)-b(n-1, k-2):
seq(seq(T(n, d), d=1..n-1), n=2..12);  # Alois P. Heinz, Aug 21 2017

gf[k_] := gf[k] = If[k == 0, x, x*E^gf[k-1]]; a[n_, k_] := n!*Coefficient[Series[gf[k], {x, 0, n+1}], x, n]; t[n_, k_] := (a[n, k] - a[n, k-1])/n; Table[t[n, k], {n, 2, 11}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Mar 18 2014, after Alois P. Heinz *)

from sympy import binomial
from sympy.core.cache import cacheit
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*j*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def T(n, k): return b(n - 1, k - 1) - b(n - 1, k - 2)
for n in range(2, 13): print([T(n, d) for d in  range(1, n)]) # Indranil Ghosh, Aug 26 2017, after Maple code

A234953(n) = Sum_{k=1..n} k*T(n,k).

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 1, 0, 3, 6, 0, 6, 0, 0, 0, 0, 0, 1, 0, 4, 24, 12, 0, 36, 24, 0, 24, 0, 0, 0, 0, 0, 0, 1, 0, 5, 80, 90, 20, 0, 200, 300, 60, 0, 300, 120, 0, 120, 0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 240, 540, 240, 30, 0, 1170, 3000, 1260, 120, 0, 3360, 2520, 360, 0, 2520, 720, 0, 720, 0

Offset: 0

Alois P. Heinz, Aug 20 2017

Positive elements in column t=1 give A034855.
Elements in rows h=0 give A023531.
Elements in rows h=1 give A059297.
Positive row sums per layer give A235595.
Positive column sums per layer give A061356.

			n h\t: 0   1   2  3  4 5 : A235595 : A061356          : A000272
-----+-------------------+---------+------------------+--------
0 0  : 1                 :         :                  : 1
-----+-------------------+---------+------------------+--------
1 0  : 0   1             :      1  :   .              :
1 1  : 0                 :         :   1              : 1
-----+-------------------+---------+------------------+--------
2 0  : 0   0   1         :      1  :   .   .          :
2 1  : 0   2             :      2  :   .              :
2 2  : 0                 :         :   2   1          : 3
-----+-------------------+---------+------------------+--------
3 0  : 0   0   0  1      :      1  :   .   .   .      :
3 1  : 0   3   6         :      9  :   .   .          :
3 2  : 0   6             :      6  :   .              :
3 3  : 0                 :         :   9   6   1      : 16
-----+-------------------+---------+------------------+--------
4 0  : 0   0   0  0  1   :      1  :   .   .   .  .   :
4 1  : 0   4  24 12      :     40  :   .   .   .      :
4 2  : 0  36  24         :     60  :   .   .          :
4 3  : 0  24             :     24  :   .              :
4 4  : 0                 :         :  64  48  12  1   : 125
-----+-------------------+---------+------------------+--------
5 0  : 0   0   0  0  0 1 :      1  :   .   .   .  . . :
5 1  : 0   5  80 90 20   :    195  :   .   .   .  .   :
5 2  : 0 200 300 60      :    560  :   .   .   .      :
5 3  : 0 300 120         :    420  :   .   .          :
5 4  : 0 120             :    120  :   .              :
5 5  : 0                 :         : 625 500 150 20 1 : 1296
-----+-------------------+---------+------------------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000012, A000142, A000272, A000551, A001477, A001788, A001854, A002378, A023531, A034855, A038154, A059297, A061356, A089946, A126804, A234953, A235595, A235596, A243014, A291204, A291336, A291529.

b:= proc(n, t, h) option remember; expand(`if`(n=0 or h=0, x^(t*n), add(
       binomial(n-1, j-1)*j*x^t*b(j-1, 0, h-1)*b(n-j, t, h), j=1..n)))
    end:
g:= (n, h)-> b(n, 1, h)-`if`(h=0, 0, b(n, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..8);

b[n_, t_, h_] := b[n, t, h] = Expand[If[n == 0 || h == 0, x^(t*n), Sum[
     Binomial[n-1, j-1]*j*x^t*b[j-1, 0, h-1]*b[n-j, t, h], {j, 1, n}]]];
g[n_, h_] := b[n, 1, h] - If[h == 0, 0, b[n, 1, h - 1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n - h}], {h, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Sum_{i=0..n} F(n,i,n-i) = A243014(n) = 1 + A038154(n).
Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000272(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A089946(n-1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A234953(n+1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1)*(n+1) * F(n,h,t) = A001854(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A235596(n+1).
F(2n,n,n) = A126804(n) for n>0.
F(n,0,n) = 1 = A000012(n).
F(n,1,1) = n = A001477(n) for n>1.
F(n,n-1,1) = n! = A000142(n) for n>0.
F(n,1,n-1) = A002378(n-1) for n>0.
F(n,2,1) = A000551(n).
F(n,3,1) = A000552(n).
F(n,4,1) = A000553(n).
F(n,1,2) = A001788(n-1) for n>2.
F(n,0,0) = A000007(n).

cp's OEIS Frontend

A133399 Triangle T(n,k)=number of forests of labeled rooted trees with n nodes, containing exactly k trees of height one, all others having height zero (n>=0, 0<=k<=floor(n/2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A235595 Triangle read by rows: the triangle in A034855, with the n-th row normalized by dividing it by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula