login
The OEIS is supported by the many generous donors 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. 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
Conjectured to be the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 3>4, 3>5} of length 5. That is, conjectured to be the number of length n permutations having no subsequences of length 5 in which the first element is the largest, and the third element is larger than the fourth and fifth elements. - Sergey Kitaev, Dec 13 2020
LINKS
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, arXiv:2312.07716 [math.CO], 2023.
Hadrien Cambazard and Nicolas 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 and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Pawel Hitczenko, Jeremy R. Johnson, and 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 and M. Püschel, In search for the optimal Walsh-Hadamard transform, Proc. ICASSP, Vol. 4, 2000, pp. 3347-3350.
Vladimir Kruchinin and 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)
D-finite with recurrence: 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 recurrence above. (End)
a(n) = Sum_{j=0..(n-1)/2} (-1)^j*2^(n-j-1)*C(n,j)*C(2*n-2*j-2,n-2*j-1)/n. - Vladimir Kruchinin, Sep 29 2020
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
(Maxima) a(n):=sum((-1)^j*2^(n-j-1)*binomial(n, j)*binomial(2*n-2*j-2, n-2*j-1), j, 0, (n-1)/2)/n /* Vladimir Kruchinin, Sep 29 2020 */
CROSSREFS
Sequence in context: A152322 A308726 A168490 * A212884 A085486 A152318
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 06:40 EDT 2024. Contains 373512 sequences. (Running on oeis4.)