This site is supported by donations to The OEIS Foundation.

 Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing. Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (p-tree) 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 p-tree of weight y_i, for 1 <= i <= k. For n = 1, the only p-tree is a single node. This definition precludes nodes with only one branch, and non-leaf nodes have weight 0. If the above is changed so that k >= 1 and y is partition of n-1, we get the trees counted by A093637. Binary p-trees 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 p-trees 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(n-i, i)))+`if`(i>1, b(n, i-1), 0)     end: a:= proc(n) option remember;       `if`(n=1, 1, add(a(k)*b(n-k, min(n-k, k)), k=1..n-1))     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[n-i, i]]] + If[i>1, b[n, i-1], 0]; a[n_] := a[n] = If[n == 1, 1, Sum[a[k]*b[n-k, Min[n-k, k] ], {k, 1, n-1}]]; Table[a[n], {n, 1, 40}] (* Jean-Franç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, n-1, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 15 11:43 EST 2019. Contains 329999 sequences. (Running on oeis4.)