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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A278677 Popularity of left children in treeshelves avoiding pattern T231. 8
1, 5, 23, 109, 544, 2876, 16113, 95495, 597155, 3929243, 27132324, 196122796, 1480531285, 11647194573, 95297546695, 809490850313, 7126717111964, 64930685865768, 611337506786061, 5940420217001199, 59502456129204083, 613689271227219015, 6510381400140132872 (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 T231 illustrated below corresponds to a treeshelf constructed from permutation 231. Popularity is the sum of a certain statistic (number of left children, in this case) over all objects of size n.

a(n) is also the sum of the last entries in all blocks of all set partitions of [n-1]. a(4) = 23 because the sum of the last entries in all blocks of all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 3+5+5+4+6  = 23. - Alois P. Heinz, Apr 24 2017

LINKS

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

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.: (z*e^z - e^z + 1)*e^(e^z-1).

a(n) = (n + 1)*b(n) - b(n+1) where b(n) is the n-th Bell number (see A000110).

Asymtotics: a(n) ~ n*b(n).

a(n) = Sum_{k=1..n-1} A285595(n-1,k)/k. - Alois P. Heinz, Apr 24 2017

EXAMPLE

Treeshelves of size 3:

      1  1          1    1       1        1

     /    \        /      \     / \      / \

    2      2      /        \   2   \    /   2

   /        \    2          2       3  3

  3          3    \        /

                   3      3

Pattern T231:

     1

    /

   /

  2

   \

    3

Treeshelves of size 3 that avoid pattern T231:

      1  1      1       1        1

     /    \      \     / \      / \

    2      2      \   2   \    /   2

   /        \      2       3  3

  3          3    /

                 3

Popularity of left children here is 5.

PROG

(Python)

## First version, simple recursion

from sympy import bell

HOW_MANY = 30

print ([ (n+1)*bell(n) - bell(n+1) for n in range(HOW_MANY)])

(Python)

## Second version by Taylor expansion

from sympy import *

from sympy.abc import z

bell = exp( exp (z) - 1)

h = (z * exp (z) - exp (z) + 1) * bell

NUMBER_OF_COEFFS = 8

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, A278678, A278679, A285595, A286897.

Sequence in context: A109877 A179598 A192810 * A017974 A244936 A017975

Adjacent sequences:  A278674 A278675 A278676 * A278678 A278679 A278680

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 October 22 12:22 EDT 2018. Contains 316446 sequences. (Running on oeis4.)