|
%I #51 Dec 15 2023 21:00:04
%S 1,5,23,109,544,2876,16113,95495,597155,3929243,27132324,196122796,
%T 1480531285,11647194573,95297546695,809490850313,7126717111964,
%U 64930685865768,611337506786061,5940420217001199,59502456129204083,613689271227219015,6510381400140132872
%N Popularity of left children in treeshelves avoiding pattern T231.
%C 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.
%C 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
%H Alois P. Heinz, <a href="/A278677/b278677.txt">Table of n, a(n) for n = 2..575</a>
%H Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki, <a href="https://arxiv.org/abs/1611.07793">Patterns in treeshelves</a>, arXiv:1611.07793 [cs.DM], 2016.
%H J. Françon, <a href="http://www.numdam.org/item/ITA_1976__10_3_35_0/">Arbres binaires de recherche : propriétés combinatoires et applications</a>, Revue française d'automatique informatique recherche opérationnelle, Informatique théorique, 10 no. 3 (1976), pp. 35-50.
%F E.g.f.: (z*e^z - e^z + 1)*e^(e^z-1).
%F a(n) = (n + 1)*b(n) - b(n+1) where b(n) is the n-th Bell number (see A000110).
%F Asymptotics: a(n) ~ n*b(n).
%F a(n) = Sum_{k=1..n-1} A285595(n-1,k)/k. - _Alois P. Heinz_, Apr 24 2017
%F a(n) = Sum_{k=1..n} Stirling2(n,k) * (n-k). - _Ilya Gutkovskiy_, Apr 06 2021
%F a(n) ~ n*Bell(n)*(1 - 1/LambertW(n)). - _Vaclav Kotesovec_, Jul 28 2021
%F a(n) = Sum_{k=n-1..(n-1)*n/2} k * A367955(n-1,k). - _Alois P. Heinz_, Dec 11 2023
%e Treeshelves of size 3:
%e 1 1 1 1 1 1
%e / \ / \ / \ / \
%e 2 2 / \ 2 \ / 2
%e / \ 2 2 3 3
%e 3 3 \ /
%e 3 3
%e Pattern T231:
%e 1
%e /
%e /
%e 2
%e \
%e 3
%e Treeshelves of size 3 that avoid pattern T231:
%e 1 1 1 1 1
%e / \ \ / \ / \
%e 2 2 \ 2 \ / 2
%e / \ 2 3 3
%e 3 3 /
%e 3
%e Popularity of left children here is 5.
%p b:= proc(n, m) option remember; `if`(n=0, [1, 0],
%p (p-> p+[0, p[1]*n])(b(n-1, m+1))+m*b(n-1, m))
%p end:
%p a:= n-> b(n-1, 0)[2]:
%p seq(a(n), n=2..24); # _Alois P. Heinz_, Dec 15 2023
%t a[n_] := (n+1) BellB[n] - BellB[n+1];
%t Table[a[n], {n, 2, 24}] (* _Jean-François Alcover_, Dec 01 2018 *)
%o (Python)
%o # First version, simple recursion
%o from sympy import bell
%o HOW_MANY = 30
%o print([(n + 1) * bell(n) - bell(n + 1) for n in range(HOW_MANY)])
%o (Python)
%o # Second version by Taylor expansion
%o from sympy import *
%o from sympy.abc import z
%o bell = exp( exp (z) - 1)
%o h = (z * exp (z) - exp (z) + 1) * bell
%o NUMBER_OF_COEFFS = 8
%o coeffs = Poly(series(h,n = NUMBER_OF_COEFFS)).coeffs()
%o coeffs.reverse()
%o # and remove first coefficient 1 that corresponds to O(n**k)
%o coeffs.pop(0)
%o print([coeffs[n]*factorial(n+2) for n in range(len(coeffs))])
%Y Cf. A000110, A000111, A000142, A001286, A008292, A131178, A278678, A278679, A285595, A286897, A367955.
%K nonn
%O 2,2
%A _Sergey Kirgizov_, Nov 26 2016
| 