1,2

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

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

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.

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

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)

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;

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 *)

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

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

Sequence in context: A152322 A308726 A168490 * A212884 A393122 A375923

Adjacent sequences: A118373 A118374 A118375 * A118377 A118378 A118379

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

approved