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!)
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
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)
# 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
Sequence in context: A083065 A137636 A027618 * A020060 A122394 A047781
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)