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
Examples
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;
Links
- Alois P. Heinz, Rows n = 1..400, flattened
Crossrefs
Programs
-
Maple
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 -
Mathematica
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 -
Python
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
Formula
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)
Comments