A291532 -id:A291532 - cp's OEIS frontend

A227774 Triangular array read by rows: T(n,k) is the number of rooted identity trees with n nodes having exactly k subtrees from the root.

1, 1, 1, 1, 1, 2, 1, 3, 3, 6, 5, 1, 12, 11, 2, 25, 22, 5, 52, 49, 12, 113, 104, 28, 2, 247, 232, 65, 4, 548, 513, 152, 13, 1226, 1159, 351, 34, 2770, 2619, 818, 91, 1, 6299, 5989, 1907, 225, 6, 14426, 13734, 4460, 571, 18, 33209, 31729, 10453, 1403, 57, 76851

Offset: 1

Geoffrey Critzer, Jul 30 2013

Row sums = A004111.

			Triangular array T(n,k) begins:
n\k:   0    1    2   3   4  ...
---+---------------------------
01 :   1;
02 :   .    1;
03 :   .    1;
04 :   .    1,   1;
05 :   .    2,   1;
06 :   .    3,   3;
07 :   .    6,   5,  1;
08 :   .   12,  11,  2;
09 :   .   25,  22,  5;
10 :   .   52,  49, 12;
11 :   .  113, 104, 28,  2;

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

Columns k=1-10 give: A004111(n-1), A227806, A227807, A227808, A227809, A227810, A227811, A227812, A227813, A227814.

Cf. A291529, A291532.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(b((i-1)$2), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, expand(
      add(x^j*binomial(b((i-1)$2), j)*g(n-i*j, i-1), j=0..n/i))))
    end:
T:= n-> `if`(n=1, 1,
    (p-> seq(coeff(p, x, k), k=1..degree(p)))(g((n-1)$2))):
seq(T(n), n=1..25);  # Alois P. Heinz, Jul 30 2013

nn=20;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0==Series[f[x]-x Product[(1+x^i)^a[i],{i,1,nn}],{x,0,nn}],x];A004111=Drop[ Flatten[Table[a[n],{n,0,nn}]/.sol],1];Map[Select[#,#>0&]&, Drop[CoefficientList[Series[x Product[(1 + y x^i)^A004111[[i]],{i,1,nn}],{x,0,nn}],{x,y}],1]]//Grid

from sympy import binomial, Poly, Symbol
from sympy.core.cache import cacheit
x=Symbol('x')
@cacheit
def b(n, i):return 1 if n==0 else 0 if i<1 else sum([binomial(b(i - 1, i - 1), j)*b(n - i*j, i - 1) for j in range(n//i + 1)])
@cacheit
def g(n, i):return 1 if n==0 else 0 if i<1 else sum([x**j*binomial(b(i - 1, i - 1), j)*g(n - i*j, i - 1) for j in range(n//i + 1)])
def T(n): return [1] if n==1 else Poly(g(n - 1, n - 1)).all_coeffs()[::-1][1:]
for n in range(1, 26): print(T(n)) # Indranil Ghosh, Aug 28 2017

G.f.: x * Product_{n>=1} (1 + y * x^n)^A004111(n).
From Alois P. Heinz, Aug 25 2017: (Start)
T(n,k) = Sum_{h=0..n-k} A291529(n-1,h,k).
Sum_{k>=1} k * T(n,k) = A291532(n-1). (End)

A291529 Number F(n,h,t) of forests of t (unlabeled) rooted identity 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, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 2, 3, 0, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 2, 5, 1, 0, 0, 5, 4, 0, 0, 4, 1, 0, 1, 0

Offset: 0

Alois P. Heinz, Aug 25 2017

Positive row sums per layer (and - with a different offset - positive elements in column t=1) give A227819.

Positive column sums per layer give A227774.

			n h\t: 0 1 2 3 4 5 : A227819 : A227774   : A004111
-----+-------------+---------+-----------+--------
0 0  : 1           :         :           : 1
-----+-------------+---------+-----------+--------
1 0  : 0 1         :       1 : .         :
1 1  : 0           :         : 1         : 1
-----+-------------+---------+-----------+--------
2 0  : 0 0 0       :       0 : . .       :
2 1  : 0 1         :       1 : .         :
2 2  : 0           :         : 1 0       : 1
-----+-------------+---------+-----------+--------
3 0  : 0 0 0 0     :       0 : . . .     :
3 1  : 0 0 1       :       1 : . .       :
3 2  : 0 1         :       1 : .         :
3 3  : 0           :         : 1 1 0     : 2
-----+-------------+---------+-----------+--------
4 0  : 0 0 0 0 0   :       0 : . . . .   :
4 1  : 0 0 0 0     :       0 : . . .     :
4 2  : 0 1 1       :       2 : . .       :
4 3  : 0 1         :       1 : .         :
4 4  : 0           :         : 2 1 0 0   : 3
-----+-------------+---------+-----------+--------
5 0  : 0 0 0 0 0 0 :       0 : . . . . . :
5 1  : 0 0 0 0 0   :       0 : . . . .   :
5 2  : 0 0 2 0     :       2 : . . .     :
5 3  : 0 2 1       :       3 : . .       :
5 4  : 0 1         :       1 : .         :
5 5  : 0           :         : 3 3 0 0 0 : 6
-----+-------------+---------+-----------+--------

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

Cf. A000007, A004111, A227774, A227819, A291203, A291204, A291336, A291532, A291559.

b:= proc(n, i, t, h) option remember; expand(`if`(n=0 or h=0 or i=1,
      `if`(n<2, x^(t*n), 0), b(n, i-1, t, h)+add(x^(t*j)*binomial(
       b(i-1$2, 0, h-1), j)*b(n-i*j, i-1, t, h), j=1..n/i)))
    end:
g:= (n, h)-> b(n$2, 1, h)-`if`(h=0, 0, b(n$2, 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..10);

b[n_, i_, t_, h_] := b[n, i, t, h] = Expand[If[n == 0 || h == 0 || i == 1, If[n < 2, x^(t*n), 0], b[n, i - 1, t, h] + Sum[x^(t*j)*Binomial[b[i - 1, i - 1, 0, h - 1], j]*b[n - i*j, i - 1, t, h], {j, 1, n/i}]]];
g[n_, h_] := b[n, n, 1, h] - If[h == 0, 0, b[n, n, 1, h - 1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[F[n, h, t], {n, 0, 10}, {h, 0, n}, {t, 0, n - h}] // Flatten (* Jean-François Alcover, Jun 04 2018, from Maple *)

Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A004111(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A291532(n).
Sum_{h=0..n-2} Sum_{t=1..n-1-h} (h+1) * F(n-1,h,t) = A291559(n).
F(n,0,0) = A000007(n).

cp's OEIS Frontend

A227774 Triangular array read by rows: T(n,k) is the number of rooted identity trees with n nodes having exactly k subtrees from the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula