This site is supported by donations to The OEIS Foundation.

 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. 17
 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. Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019. 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 16 19:43 EDT 2019. Contains 324155 sequences. (Running on oeis4.)