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. 16
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.

Also the number of series-reduced enriched plane trees of weight n. A series-reduced enriched plane tree of weight n is either the number n itself or a finite sequence of at least two series-reduced enriched plane trees, one of each part of an integer composition of n. For example, the a(3) = 6 trees are: 3, (21), (12), (111), ((11)1), (1(11)). - Gus Wiseman, Sep 11 2018

LINKS

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

Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.

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

From Gus Wiseman, Sep 11 2018: (Start)

The a(4) = 24 series-reduced enriched plane trees:

  4,

  (31), (13), (22), (211), (121), (112), (1111),

  ((21)1), ((12)1), (1(21)), (1(12)), (2(11)), ((11)2),

  ((111)1), (1(111)), ((11)(11)), ((11)11), (1(11)1), (11(11)),

  (((11)1)1), ((1(11))1), (1((11)1)), (1(1(11))).

(End)

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 *)

urp[n_]:=Prepend[Join@@Table[Tuples[urp/@ptn], {ptn, Join@@Permutations/@Select[IntegerPartitions[n], Length[#]>1&]}], n];

Table[Length[urp[n]], {n, 7}] (* Gus Wiseman, Sep 11 2018 *)

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. A000108, A000311, A001003, A005804, A007317, A007853, A032171, A032200, A143363, A289501, A317852.

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 October 19 15:49 EDT 2018. Contains 316365 sequences. (Running on oeis4.)