A052319 Number of increasing rooted trimmed trees with n nodes.

1, 1, 1, 2, 7, 28, 131, 720, 4513, 31824, 249513, 2151744, 20242983, 206313024, 2264425179, 26628836352, 334022337153, 4451717814528, 62820790592913, 935750983412736, 14672143677452679, 241555066200437760

Offset: 1

Author

Christian G. Bower, Dec 11 1999

Keywords

• nonn
• eigen

Comments

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.

A trimmed tree is a tree with a forbidden limb of length 2.

A tree with a forbidden limb of length k is a tree where the path from any leaf inward hits a branching node or another leaf within k steps.

Number of permutations on [n+1] beginning with 12 and avoiding a consecutive 132 pattern (n>=1). For example, a(4)=2 counts 12345, 12453. - Ralf Stephan, Apr 25 2004

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..465
• M. E. Jones and J. B. Remmel, Pattern matching in the cycle structures of permutations, Pure Math. Appl. (PU.M.A.), 22 (2011) 173-208.
• S. Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003).
• S. Kitaev and T. Mansour, Simultaneous avoidance of generalized patterns, arXiv:math/0205182 [math.CO], 2002.
• Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021, p. 7.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A002955, A002988-A002992, A052318-A052329.

Programs

Maple

seq(n! * coeff(series(-log(1-sqrt(Pi/2)*erf(x/sqrt(2))), x, n+1), x, n), n=1..20) # Vaclav Kotesovec, Jan 07 2014

Mathematica

Rest[CoefficientList[Series[-Log[1-Sqrt[Pi/2]*Erf[x/Sqrt[2]]], {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Jan 07 2014 *)

Formula

E.g.f.: A(x) = 1/B(-x) where B'(x) is e.g.f. of A006882 and B(0) = 1.

E.g.f.: A(x) satisfies A'(x) = exp(A(x)-x^2/2).

E.g.f.: exp(-x^2/2)/(1-int[0..x, exp(-x^2/2)]). - Ralf Stephan, Apr 25 2004

E.g.f.: -log(1-sqrt(Pi/2)*erf(x/sqrt(2))). - Vaclav Kotesovec, Jan 07 2014

Limit n->infinity (a(n)/n!)^(1/n) = 1/(sqrt(2)*InverseErf(sqrt(2/Pi))) = 1/A240885 = 0.7839769312035474991... - Vaclav Kotesovec, Jan 07 2014

a(n) ~ (n-1)! / (sqrt(2)*InverseErf(sqrt(2/Pi)))^n. - Vaclav Kotesovec, Aug 22 2014

Extensions

Formula updated by Christian G. Bower, Mar 06 2001