login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A196545 Number of weakly ordered plane trees with n leaves. 81
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 November 24 22:57 EST 2020. Contains 338616 sequences. (Running on oeis4.)