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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A196545 Number of weakly ordered plane trees with n leaves. 82

%I

%S 1,1,2,5,12,34,92,277,806,2500,7578,24198,75370,243800,776494,2545777,

%T 8223352,27221690,88984144,296856400,979829772,3287985078,10934749788,

%U 36912408342,123519937044,418650924886,1408867195252,4794243983204,16205061000480

%N Number of weakly ordered plane trees with n leaves.

%C 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.

%C 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.

%H Alois P. Heinz, <a href="/A196545/b196545.txt">Table of n, a(n) for n = 1..1000</a>

%H Gus Wiseman, <a href="http://www.youtube.com/watch?v=r49O36wKCNM">All 277 weakly ordered plane trees of weight 8</a>

%F 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.

%F 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.

%e 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).

%p b:= proc(n, i) option remember;

%p `if`(i>n, 0, a(i)*`if`(i=n, 1, b(n-i, i)))+`if`(i>1, b(n, i-1), 0)

%p end:

%p a:= proc(n) option remember;

%p `if`(n=1, 1, add(a(k)*b(n-k, min(n-k, k)), k=1..n-1))

%p end:

%p seq(a(n), n=1..40); # _Alois P. Heinz_, Jul 06 2012

%t PTNum[n_] := PTNum[n] =

%t If[n === 1, 1, Plus @@ Function[y,

%t Times @@ PTNum /@ y] /@ Rest[Partitions[n]]]; Array[PTNum, 20]

%t (* Second program: *)

%t 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];

%t a[n_] := a[n] = If[n == 1, 1, Sum[a[k]*b[n-k, Min[n-k, k] ], {k, 1, n-1}]];

%t Table[a[n], {n, 1, 40}] (* _Jean-Fran├žois Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)

%o (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

%o (Sage)

%o @cached_function

%o def A196545(n):

%o if n == 1: return 1

%o return sum(prod(A196545(t) for t in p) for p in Partitions(n,min_length=2))

%o # _D. S. McNeil_, Oct 03 2011

%Y Cf. A000041, A063834, A093637, A000992.

%K nonn

%O 1,3

%A _Gus Wiseman_, Oct 03 2011

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 June 15 21:26 EDT 2021. Contains 345051 sequences. (Running on oeis4.)