login
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

%I #76 Aug 06 2024 09:51:57

%S 1,2,6,24,112,568,3032,16768,95200,551616,3248704,19389824,117021824,

%T 712934784,4378663296,27081760768,168530142720,1054464293888,

%U 6629484729344,41860283723776,265346078982144,1687918305128448,10771600724946944,68941213290561536

%N 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.

%C 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.

%C 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

%C 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

%C This conjecture has been proven. It can be restated as the number of size n permutations avoiding 51423, 51432, 52413, 52431, 53412, 53421, 54312, 54321. There are twelve sets of permutations avoiding eight size five permutations that are known to match this sequence. A further four are conjectured to match this sequence. - _Christian Bean_, Jul 24 2024

%H G. C. Greubel, <a href="/A118376/b118376.txt">Table of n, a(n) for n = 1..1000</a>

%H Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://permpal.com/perms/search_params/?we_type=cfs&amp;wilf_equivalence=01234%2C+01243%2C+02134%2C+02143%2C+02314%2C+02341%2C+02413%2C+02431">PermPAL database</a>.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.10297">Generalized Eulerian Triangles and Some Special Production Matrices</a>, arXiv:1803.10297 [math.CO], 2018.

%H Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://doi.org/10.37236/12686">Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding</a>, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); <a href="https://arxiv.org/abs/2312.07716">arXiv preprint</a>, arXiv:2312.07716 [math.CO], 2023.

%H Hadrien Cambazard and Nicolas Catusse, <a href="http://arxiv.org/abs/1512.06649">Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane</a>, arXiv preprint arXiv:1512.06649 [cs.DS], 2015.

%H S. B. Ekhad and M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt">Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, (2017).

%H Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.

%H Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

%H Pawel Hitczenko, Jeremy R. Johnson, and Hung-Jen Huang, <a href="http://dx.doi.org/10.1016/j.tcs.2005.09.074">Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform</a>, Theoretical Computer Science, Vol. 352, 2006, pp. 8-30.

%H J. R. Johnson and M. Püschel, <a href="https://citeseerx.ist.psu.edu/pdf/4bfadc40a98b912820a61e9a307ef163130f8be1">In search for the optimal Walsh-Hadamard transform</a>, Proc. ICASSP, Vol. 4, 2000, pp. 3347-3350.

%H Vladimir Kruchinin and D. V. Kruchinin, <a href="http://arxiv.org/abs/1103.2582">Composita and their properties </a>, arXiv:1103.2582 [math.CO], 2011-2013.

%F Recurrence: T(1) = 1; For n > 1, T(n) = 1 + Sum_{n=n1+...+nt} T(n1)*...*T(nt).

%F G.f.: (-1+(1-8*z+8*z^2)^(1/2))/(-4+4*z).

%F From _Vladimir Kruchinin_, Sep 03 2010: (Start)

%F O.g.f.: A(x) = A001003(x/(1-x)).

%F a(n) = Sum_{k=1..n} binomial(n-1,k-1)*A001003(k), n>0. (End)

%F 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

%F 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

%F From _Peter Bala_, Jun 17 2015: (Start)

%F With offset 0, binomial transform of A001003.

%F 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.

%F 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)

%F 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

%e T(3) = 6 because there are six trees

%e 3 3 3 3 3 3

%e 2 1 2 1 1 2 1 2 1 1 1

%e 1 1 1 1

%e From _Gus Wiseman_, Sep 11 2018: (Start)

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

%e 4,

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

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

%e ((111)1), (1(111)), ((11)(11)), ((11)11), (1(11)1), (11(11)),

%e (((11)1)1), ((1(11))1), (1((11)1)), (1(1(11))).

%e (End)

%p 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;

%t Rest[CoefficientList[Series[(Sqrt[1-8*x+8*x^2]-1)/(4*x-4), {x, 0, 20}], x]] (* _Vaclav Kotesovec_, Feb 03 2014 *)

%t 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_ *)

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

%t Table[Length[urp[n]],{n,7}] (* _Gus Wiseman_, Sep 11 2018 *)

%o (PARI) x='x+O('x^25); Vec((sqrt(1-8*x+8*x^2) - 1)/(4*x-4)) \\ _G. C. Greubel_, Feb 08 2017

%o (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 */

%Y Cf. A000108, A000311, A001003, A005804, A007317, A007853, A032171, A032200, A143363, A289501, A317852.

%K nonn

%O 1,2

%A Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006