|
|
A278677
|
|
Popularity of left children in treeshelves avoiding pattern T231.
|
|
11
|
|
|
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
|
|
|
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).
Asymptotics: a(n) ~ n*b(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 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.
|
|
MAPLE
|
b:= proc(n, m) option remember; `if`(n=0, [1, 0],
(p-> p+[0, p[1]*n])(b(n-1, m+1))+m*b(n-1, m))
end:
a:= n-> b(n-1, 0)[2]:
|
|
MATHEMATICA
|
a[n_] := (n+1) BellB[n] - BellB[n+1];
|
|
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, A367955.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|