login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A278679 Popularity of left children in treeshelves avoiding pattern T213. 5
1, 5, 24, 128, 770, 5190, 38864, 320704, 2894544, 28382800, 300575968, 3419882304, 41612735632, 539295974000, 7417120846080, 107904105986048, 1655634186628352, 26721851169634560, 452587550053179392, 8026445538106839040, 148751109541600495104 (list; graph; refs; listen; history; text; internal format)
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
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
Sequence in context: A058120 A271544 A275267 * A000349 A327118 A353735
KEYWORD
nonn
AUTHOR
Sergey Kirgizov, Nov 26 2016
EXTENSIONS
More terms from Alois P. Heinz, Oct 27 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 11:48 EDT 2024. Contains 373701 sequences. (Running on oeis4.)