A301422 Regular triangle where T(n,k) is the number of r-trees of size n with k leaves.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 19, 14, 5, 1, 0, 1, 12, 36, 40, 21, 6, 1, 0, 1, 16, 65, 102, 75, 30, 7, 1, 0, 1, 20, 106, 223, 224, 123, 40, 8, 1, 0, 1, 25, 168, 457, 604, 439, 191, 52, 9, 1, 0, 1, 30, 248, 847, 1433, 1346, 764, 276

Offset: 1

Author

Gus Wiseman, Mar 20 2018

Keywords

• nonn
• tabl

Comments

An r-tree (A093637) of size n > 0 is a finite sequence of r-trees with weakly decreasing sizes summing to n - 1. This is a similar construction to p-trees (A196545) except that r-trees are not required to be series-reduced and are weighted by all nodes (including the root) rather than just the leaves.

Examples

			Triangle begins:
  1
  1   0
  1   1   0
  1   2   1   0
  1   4   3   1   0
  1   6   8   4   1   0
  1   9  19  14   5   1   0
  1  12  36  40  21   6   1   0
  1  16  65 102  75  30   7   1   0
  1  20 106 223 224 123  40   8   1   0
  1  25 168 457 604 439 191  52   9   1   0
  ...
The T(6,3) = 8 r-trees: (((ooo))), (((oo)o)), (((o)oo)), (((oo))o), (((o)o)o), ((oo)(o)), (((o))oo), ((o)(o)o).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275

Crossrefs

Cf. A000081, A003238, A004111, A032305, A055277, A093637, A127524, A196545, A289501, A290689, A291443, A297791, A300443, A301342-A301345, A301364.

Programs

Mathematica

rtrees[n_]:=Join@@Table[Tuples[rtrees/@y],{y,IntegerPartitions[n-1]}];
Table[Length[Select[rtrees[n],Count[#,{},{-2}]===k&]],{n,8},{k,n}]

PARI

A(n)={my(v=vector(n)); v[1]=y; for(n=2, n, v[n] = polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x^n)), n-1)); vector(n, k, Vecrev(v[k]/y,k))}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 26 2018