A278679 Popularity of left children in treeshelves avoiding pattern T213.

1, 5, 24, 128, 770, 5190, 38864, 320704, 2894544, 28382800, 300575968, 3419882304, 41612735632, 539295974000, 7417120846080, 107904105986048, 1655634186628352, 26721851169634560, 452587550053179392, 8026445538106839040, 148751109541600495104

Offset

2,2

Comments

Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link. Classical Françon's bijection maps bijectively treeshelves into permutations. Pattern T213 illustrated below corresponds to a treeshelf constructed from permutation 213. Popularity is the sum of a certain statistic (number of left children, in this case) over all objects of size n.

Links

Table of n, a(n) for n=2..22.

Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Patterns in treeshelves, arXiv:1611.07793 [cs.DM], 2016.

J. Françon, Arbres binaires de recherche : propriétés combinatoires et applications, Revue française d'automatique informatique recherche opérationnelle, Informatique théorique, 10 no. 3 (1976), p. 35-50.

Formula

E.g.f.: (e^(sqrt(2)*z) * (4*z-4) - (sqrt(2)-2)*e^(2*sqrt(2)*z) + sqrt(2) + 2) / ((sqrt(2)-2)*e^(sqrt(2)*z) + 2 + sqrt(2))^2.

Asymptotic: n * (sqrt(2) / log(2*sqrt(2)+3) )^(n+1).

Example

Treeshelves of size 3:
      1  1          1    1       1        1
     /    \        /      \     / \      / \
    2      2      /        \   2   \    /   2
   /        \    2          2       3  3
  3          3    \        /
                   3      3
Pattern T213:
    1
   / \
  2   \
       3
Treeshelves of size 3 that avoid pattern T213:
      1  1          1    1        1
     /    \        /      \      / \
    2      2      /        \    /   2
   /        \    2          2  3
  3          3    \        /
                   3      3
Popularity of left children is 5.

Mathematica

terms = 21;
egf = (E^(Sqrt[2] z)(4z - 4) - (Sqrt[2] - 2) E^(2 Sqrt[2] z) + Sqrt[2] + 2)/((Sqrt[2] - 2) E^(Sqrt[2] z) + 2 + Sqrt[2])^2;
CoefficientList[egf + O[z]^(terms + 2), z]*Range[0, terms + 1]! // Round // Drop[#, 2]& (* Jean-François Alcover, Jan 26 2019 *)

Prog

(Python)
## by Taylor expansion
from sympy import *
from sympy.abc import z
h = (exp(sqrt(2)*z) * (4*z-4) - (sqrt(2)-2)*exp(2*sqrt(2)*z) + sqrt(2) + 2) / ((sqrt(2)-2)*exp(sqrt(2)*z) + 2 + sqrt(2))**2
NUMBER_OF_COEFFS = 20
coeffs = Poly(series(h, n = NUMBER_OF_COEFFS)).coeffs()
coeffs.reverse()
## and remove first coefficient 1 that corresponds to O(n**k)
coeffs.pop(0)
print([coeffs[n]*factorial(n+2) for n in range(len(coeffs))])

Crossrefs

Cf. A000110, A000111, A000142, A001286, A008292, A131178, A278677, A278678.

Sequence in context: A058120 A271544 A275267 * A000349 A327118 A353735

Adjacent sequences: A278676 A278677 A278678 * A278680 A278681 A278682

Keyword

nonn

Author

Sergey Kirgizov, Nov 26 2016

Extensions

More terms from Alois P. Heinz, Oct 27 2017

Status

approved