cp's OEIS Frontend

A278678 Popularity of left children in treeshelves avoiding pattern T321.

%I A278678 #29 Mar 23 2020 06:46:26
%S A278678 1,4,19,94,519,3144,20903,151418,1188947,10064924,91426347,887296422,
%T A278678 9164847535,100398851344,1162831155151,14198949045106,182317628906283,
%U A278678 2455925711626404,34632584722468115,510251350142181470,7840215226100517191,125427339735162102104
%N A278678 Popularity of left children in treeshelves avoiding pattern T321.
%C A278678 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.
%H A278678 Alois P. Heinz, <a href="/A278678/b278678.txt">Table of n, a(n) for n = 2..483</a>
%H A278678 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 A278678 J. Françon, <a href="http://www.numdam.org/item/?id=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 A278678 E.g.f.: (-sin(z) + 1 + (z-1)*cos(z))/ (1-sin(z))^2.
%F A278678 a(n) = (n+1)*e(n) - e(n+1), where e(n) is the n-th Euler number (see A000111).
%F A278678 Asymptotic: a(n) ~ 8*(Pi-2) / Pi^3 * n^2 * (2/Pi)^n.
%e A278678 Treeshelves of size 3:
%e A278678       1  1          1    1       1        1
%e A278678      /    \        /      \     / \      / \
%e A278678     2      2      /        \   2   \    /   2
%e A278678    /        \    2          2       3  3
%e A278678   3          3    \        /
%e A278678                    3      3
%e A278678 Pattern T321:
%e A278678       1
%e A278678      /
%e A278678     2
%e A278678    /
%e A278678   3
%e A278678 Treeshelves of size 3 that avoid pattern T321:
%e A278678   1          1    1       1        1
%e A278678    \        /      \     / \      / \
%e A278678     2      /        \   2   \    /   2
%e A278678      \    2          2       3  3
%e A278678       3    \        /
%e A278678             3      3
%e A278678 Popularity of left children is 4.
%p A278678 b:= proc(u, o) option remember; `if`(u+o=0, 1,
%p A278678       add(b(o-1+j, u-j), j=1..u))
%p A278678     end:
%p A278678 a:= n-> (n+1)*b(n+1, 0)-b(n+2, 0):
%p A278678 seq(a(n), n=2..25);  # _Alois P. Heinz_, Oct 27 2017
%t A278678 b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[o-1+j, u-j], {j, 1, u}]];
%t A278678 a[n_] := (n+1)*b[n+1, 0] - b[n+2, 0];
%t A278678 Table[a[n], {n, 2, 25}] (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)
%o A278678 (Python)
%o A278678 # by Taylor expansion
%o A278678 from sympy import *
%o A278678 from sympy.abc import z
%o A278678 h = (-sin(z) + 1 + (z-1)*cos(z))/ (1-sin(z))**2
%o A278678 NUMBER_OF_COEFFS = 20
%o A278678 coeffs = Poly(series(h,n = NUMBER_OF_COEFFS)).coeffs()
%o A278678 coeffs.reverse()
%o A278678 # and remove first coefficient 1 that corresponds to O(n**k)
%o A278678 coeffs.pop(0)
%o A278678 print([coeffs[n]*factorial(n+2) for n in range(len(coeffs))])
%Y A278678 Cf. A000110, A000111, A000142, A001286, A008292, A131178, A278677, A278679.
%K A278678 nonn
%O A278678 2,2
%A A278678 _Sergey Kirgizov_, Nov 26 2016