A278678 Popularity of left children in treeshelves avoiding pattern T321.

1, 4, 19, 94, 519, 3144, 20903, 151418, 1188947, 10064924, 91426347, 887296422, 9164847535, 100398851344, 1162831155151, 14198949045106, 182317628906283, 2455925711626404, 34632584722468115, 510251350142181470, 7840215226100517191, 125427339735162102104

Offset: 2

Author

Sergey Kirgizov, Nov 26 2016

Keywords

• nonn

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.

Examples

			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.
		

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

Crossrefs

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

Programs

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 *)

Python

# 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))])

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.