login
This site is supported by donations to The OEIS Foundation.

 

Logo

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.

License Agreements, Terms of Use, Privacy Policy. .

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