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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A118376 Number of all trees of weight n, where nodes have positive integer weights and the sum of the weights of the children of a node is equal to the weight of the node. 3
1, 2, 6, 24, 112, 568, 3032, 16768, 95200, 551616, 3248704, 19389824, 117021824, 712934784, 4378663296, 27081760768, 168530142720, 1054464293888, 6629484729344, 41860283723776, 265346078982144, 1687918305128448, 10771600724946944, 68941213290561536 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The number of trees with leaf nodes equal to 1 is counted by the sequence A001003 of super-Catalan numbers. The number of binary trees is counted by the sequence A007317 and the number of binary trees with leaf nodes equal to 1 is counted by the sequence A000108 of Catalan numbers.

LINKS

G. C. Greubel, Table of n, a(n) for n = 1..1000

H. Cambazard, N. Catusse, Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane, arXiv preprint arXiv:1512.06649 [cs.DS], 2015.

S. B. Ekhad, M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)

Pawel Hitczenko, Jeremy R. Johnson, Hung-Jen Huang, Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Theoretical Computer Science, Vol. 352, 2006, pp. 8-30.

J. R. Johnson, M. Püschel, In search for the optimal Walsh-Hadamard transform, Proc. ICASSP, Vol. 4, 2000, pp. 3347-3350.

Vladimir Kruchinin, D. V. Kruchinin, Composita and their properties , arXiv:1103.2582 [math.CO], 2011-2013.

FORMULA

Recurrence: T(1) = 1; For n > 1, T(n) = 1 + sum_{n=n1+...+nt} T(n1)*...*T(nt).

G.f.: (-1+(1-8*z+8*z^2)^(1/2))/(-4+4*z).

From Vladimir Kruchinin, Sep 03 2010: (Start)

O.g.f.: A(x) = A001003(x/(1-x)).

a(n) = sum_{k=1..n} binomial(n-1,k-1)*A001003(k), n>0. (End)

Conjecture: n*a(n) + 3*(-3*n+4)*a(n-1) + 4*(4*n-9)*a(n-2) + 8*(-n+3)*a(n-3) = 0. - R. J. Mathar, Sep 27 2013

a(n) ~ sqrt(sqrt(2)-1) * 2^(n-1/2) * (2+sqrt(2))^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 03 2014

From Peter Bala, Jun 17 2015: (Start)

With offset 0, binomial transform of A001003.

O.g.f. A(x) = series reversion of x*(2*x - 1)/(2*x^2 - 1); 2*(1 - x)*A^2(x) - A(x) + x = 0.

A(x) satisfies the differential equation (x - 9*x^2 + 16*x^3 - 8*x^4)*A'(x) + x*(3 - 4*x)*A(x) + x*(2*x - 1) = 0. Extracting coefficients gives Mathar's conjectured recurrence above. (End)

EXAMPLE

T(3) = 6 because there are six trees

3 3 3 3 3 3

2 1 2 1 1 2 1 2 1 1 1

1 1 1 1

MAPLE

T := proc(n) option remember; local C, s, p, tp, k, i; if n = 1 then return 1; else s := 1; for k from 2 to n do C := combinat[composition](n, k); for p in C do tp := map(T, p); s := s + mul(tp[i], i=1..nops(tp)); end do; end do; end if; return s; end;

MATHEMATICA

Rest[CoefficientList[Series[(Sqrt[1-8*x+8*x^2]-1)/(4*x-4), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 03 2014 *)

a[n_] := 1+Sum[Binomial[n-1, k-1]*Hypergeometric2F1[2-k, k+1, 2, -1], {k, 2, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Apr 03 2015, after Vladimir Kruchinin *)

PROG

(PARI) x='x+O('x^25); Vec((sqrt(1-8*x+8*x^2) - 1)/(4*x-4)) \\ G. C. Greubel, Feb 08 2017

CROSSREFS

Cf. A001003, A007317, A000108.

Sequence in context: A177521 A152322 A168490 * A212884 A085486 A152318

Adjacent sequences:  A118373 A118374 A118375 * A118377 A118378 A118379

KEYWORD

nonn

AUTHOR

Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 15:02 EST 2018. Contains 299380 sequences. (Running on oeis4.)