login
This site is supported by donations 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

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

Jean-Luc Baril, Sergey Kirgizov, 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.

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 A036919 A020067

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 14:07 EDT 2018. Contains 316236 sequences. (Running on oeis4.)