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.
1, 2, 6, 24, 112, 568, 3032, 16768, 95200, 551616, 3248704, 19389824, 117021824, 712934784, 4378663296, 27081760768, 168530142720, 1054464293888, 6629484729344, 41860283723776, 265346078982144, 1687918305128448, 10771600724946944, 68941213290561536
Offset: 1
Keywords
Examples
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)
Links
- G. C. Greubel, Table of n, a(n) for n = 1..1000
- Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, PermPAL database.
- 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, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, 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.
- S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
- 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.
Crossrefs
Programs
-
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 *) -
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 */
-
PARI
x='x+O('x^25); Vec((sqrt(1-8*x+8*x^2) - 1)/(4*x-4)) \\ G. C. Greubel, Feb 08 2017
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
Comments