|
| |
|
|
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
|
|
|
|
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).
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
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
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
|
Cf. A000108, A000311, A001003, A005804, A007317, A007853, A032171, A032200, A143363, A289501, A317852.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006
|
|
|
STATUS
|
approved
|
| |
|
|
