login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A278678 Popularity of left children in treeshelves avoiding pattern T321. 6
1, 4, 19, 94, 519, 3144, 20903, 151418, 1188947, 10064924, 91426347, 887296422, 9164847535, 100398851344, 1162831155151, 14198949045106, 182317628906283, 2455925711626404, 34632584722468115, 510251350142181470, 7840215226100517191, 125427339735162102104 (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 T321 illustrated below corresponds to a treeshelf constructed from permutation 321. Popularity is the sum of a certain statistic (number of left children, in this case) over all objects of size n.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 2..483

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), pp. 35-50

FORMULA

E.g.f.: (-sin(z) + 1 + (z-1)*cos(z))/ (1-sin(z))^2.

a(n) = (n+1)*e(n) - e(n+1), where e(n) is the n-th Euler number (see A000111).

Asymptotic: a(n) ~ 8*(Pi-2) / Pi^3 * n^2 * (2/Pi)^n.

EXAMPLE

Treeshelves of size 3:

      1  1          1    1       1        1

     /    \        /      \     / \      / \

    2      2      /        \   2   \    /   2

   /        \    2          2       3  3

  3          3    \        /

                   3      3

Pattern T321:

      1

     /

    2

   /

  3

Treeshelves of size 3 that avoid pattern T321:

  1          1    1       1        1

   \        /      \     / \      / \

    2      /        \   2   \    /   2

     \    2          2       3  3

      3    \        /

            3      3

Popularity of left children is 4.

MAPLE

b:= proc(u, o) option remember; `if`(u+o=0, 1,

      add(b(o-1+j, u-j), j=1..u))

    end:

a:= n-> (n+1)*b(n+1, 0)-b(n+2, 0):

seq(a(n), n=2..25);  # Alois P. Heinz, Oct 27 2017

MATHEMATICA

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[o-1+j, u-j], {j, 1, u}]];

a[n_] := (n+1)*b[n+1, 0] - b[n+2, 0];

Table[a[n], {n, 2, 25}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

PROG

(Python)

2## by Taylor expansion

from sympy import *

from sympy.abc import z

h = (-sin(z) + 1 + (z-1)*cos(z))/ (1-sin(z))**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, A278679.

Sequence in context: A083065 A137636 A027618 * A020060 A122394 A047781

Adjacent sequences:  A278675 A278676 A278677 * A278679 A278680 A278681

KEYWORD

nonn

AUTHOR

Sergey Kirgizov, Nov 26 2016

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 February 22 13:55 EST 2018. Contains 299454 sequences. (Running on oeis4.)