

A196545


Number of weakly ordered plane trees with n leaves.


66



1, 1, 2, 5, 12, 34, 92, 277, 806, 2500, 7578, 24198, 75370, 243800, 776494, 2545777, 8223352, 27221690, 88984144, 296856400, 979829772, 3287985078, 10934749788, 36912408342, 123519937044, 418650924886, 1408867195252, 4794243983204, 16205061000480
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A weakly ordered plane tree (ptree) of weight n > 1 is a sequence (t_1, t_2, ..., t_k) where k > 1 and for some integer partition y of length k and sum n, the term t_i is a ptree of weight y_i, for 1 <= i <= k. For n = 1, the only ptree is a single node.
This definition precludes nodes with only one branch, and nonleaf nodes have weight 0. If the above is changed so that k >= 1 and y is partition of n1, we get the trees counted by A093637. Binary ptrees are counted by A000992.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Gus Wiseman, All 277 weakly ordered plane trees of weight 8


FORMULA

a(1) = 1; for n > 1, a(n) = Sum_{y} Product_{i} a(y_i) where the sum is over all partitions of n with at least two parts.
The generating function is characterized by the formal equation 1 + 2*S(x) = x + 1/P(x) where S(x) = Sum_{n>0} a(n)*x^n and P(x) = Product_{n>0} (1  a(n)*x^n) are the formal infinite series and formal infinite product with a(n) as coefficients and roots respectively.


EXAMPLE

Let o denote a single node. The 12 ptrees of weight 5 are: ((((oo)o)o)o), (((ooo)o)o), (((oo)(oo))o), (((oo)oo)o), ((oooo)o), (((oo)o)(oo)), ((ooo)(oo)), (((oo)o)oo), ((ooo)oo), ((oo)(oo)o), ((oo)ooo), (ooooo).


MAPLE

b:= proc(n, i) option remember;
`if`(i>n, 0, a(i)*`if`(i=n, 1, b(ni, i)))+`if`(i>1, b(n, i1), 0)
end:
a:= proc(n) option remember;
`if`(n=1, 1, add(a(k)*b(nk, min(nk, k)), k=1..n1))
end:
seq(a(n), n=1..40); # Alois P. Heinz, Jul 06 2012


MATHEMATICA

PTNum[n_] := PTNum[n] =
If[n === 1, 1, Plus @@ Function[y,
Times @@ PTNum /@ y] /@ Rest[Partitions[n]]]; Array[PTNum, 20]
b[n_, i_] := b[n, i] = If[i>n, 0, a[i]*If[i == n, 1, b[ni, i]]] + If[i>1, b[n, i1], 0]; a[n_] := a[n] = If[n == 1, 1, Sum[a[k]*b[nk, Min[nk, k] ], {k, 1, n1}]]; Table[a[n], {n, 1, 40}] (* JeanFrançois Alcover, Nov 05 2015, after Alois P. Heinz *)


PROG

(PARI) seq(n)={my(v=vector(n)); v[1] = 1; for(n=2, n, v[n] = polcoef(1/prod(k=1, n1, 1  v[k]*x^k + O(x*x^n)), n)); v} \\ Andrew Howroyd, Aug 26 2018
(Sage)
@cached_function
def A196545(n):
....if n == 1: return 1
....return sum(prod(A196545(t) for t in p) for p in Partitions(n, min_length=2))
# D. S. McNeil, Oct 03 2011


CROSSREFS

Cf. A000041, A063834, A093637, A000992.
Sequence in context: A209216 A076864 A209798 * A032292 A151408 A121956
Adjacent sequences: A196542 A196543 A196544 * A196546 A196547 A196548


KEYWORD

nonn


AUTHOR

Gus Wiseman, Oct 03 2011


STATUS

approved



