cp's OEIS Frontend

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.

%I A118376 #82 Feb 20 2025 10:22:59
%S A118376 1,2,6,24,112,568,3032,16768,95200,551616,3248704,19389824,117021824,
%T A118376 712934784,4378663296,27081760768,168530142720,1054464293888,
%U A118376 6629484729344,41860283723776,265346078982144,1687918305128448,10771600724946944,68941213290561536
%N 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.
%C A118376 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 A118376 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 A118376 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 A118376 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 A118376 G. C. Greubel, <a href="/A118376/b118376.txt">Table of n, a(n) for n = 1..1000</a>
%H A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 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 A118376 Recurrence: T(1) = 1; For n > 1, T(n) = 1 + Sum_{n=n1+...+nt} T(n1)*...*T(nt).
%F A118376 G.f.: (-1+(1-8*z+8*z^2)^(1/2))/(-4+4*z).
%F A118376 From _Vladimir Kruchinin_, Sep 03 2010: (Start)
%F A118376 O.g.f.: A(x) = A001003(x/(1-x)).
%F A118376 a(n) = Sum_{k=1..n} binomial(n-1,k-1)*A001003(k), n>0. (End)
%F A118376 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 A118376 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 A118376 From _Peter Bala_, Jun 17 2015: (Start)
%F A118376 With offset 0, binomial transform of A001003.
%F A118376 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 A118376 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 A118376 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 A118376 T(3) = 6 because there are six trees
%e A118376   3    3      3     3     3       3
%e A118376       2 1    2 1   1 2   1 2    1 1 1
%e A118376             1 1           1 1
%e A118376 From _Gus Wiseman_, Sep 11 2018: (Start)
%e A118376 The a(4) = 24 series-reduced enriched plane trees:
%e A118376   4,
%e A118376   (31), (13), (22), (211), (121), (112), (1111),
%e A118376   ((21)1), ((12)1), (1(21)), (1(12)), (2(11)), ((11)2),
%e A118376   ((111)1), (1(111)), ((11)(11)), ((11)11), (1(11)1), (11(11)),
%e A118376   (((11)1)1), ((1(11))1), (1((11)1)), (1(1(11))).
%e A118376 (End)
%p A118376 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 A118376 Rest[CoefficientList[Series[(Sqrt[1-8*x+8*x^2]-1)/(4*x-4), {x, 0, 20}], x]] (* _Vaclav Kotesovec_, Feb 03 2014 *)
%t A118376 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 A118376 urp[n_]:=Prepend[Join@@Table[Tuples[urp/@ptn],{ptn,Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>1&]}],n];
%t A118376 Table[Length[urp[n]],{n,7}] (* _Gus Wiseman_, Sep 11 2018 *)
%o A118376 (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 A118376 (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 A118376 Cf. A000108, A000311, A001003, A005804, A007317, A007853, A032171, A032200, A143363, A289501, A317852.
%K A118376 nonn
%O A118376 1,2
%A A118376 Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006