|
%I #25 Nov 19 2021 05:05:39
%S 1,2,4,9,22,56,147,396,1088,3036,8582,24524,70727,205594,601756,
%T 1771937,5245544,15602496,46606356,139753120,420520000,1269361000,
%U 3842722454,11663928644,35490451807,108232655126,330760284892
%N Number of {2-1-3, 2'^e-31}-avoiding permutations of size n (see definition in the Elizalde paper).
%C a(n) is the number of Dyck paths of semilength n for which all non-terminal descents are of odd length. For example, a(3) = 4 counts all 5 Dyck paths of semilength 3 except UUDDUD and a(4) = 9 counts, among others, UUUDUDDD and UUDUDUDD but not UUDDUUDD. - _David Callan_, Nov 13 2021
%H David Callan, <a href="/A143017/a143017.pdf">Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS</a>
%H S. Elizalde, <a href="http://arxiv.org/abs/0707.4633">Generating trees for permutations avoiding generalized patterns</a>, arXiv:0707.4633 [math.CO], 2007; Annals of Combinatorics 11 (2007), 435-458.
%F a(n) = (1/n)*Sum_{k=0..floor(n/2)} 2*binomial(n,2k)*binomial(n-k,k-1) + n*binomial(n,2k+1)*binomial(n-k,k)/(n-k).
%F G.f. G(x) satisfies x*G^3 + (4x-2)*G^2 + (4x-1)*G + x = 0.
%F Conjecture: -8*n*(n+1)*a(n) + 4*n*(2*n+5)*a(n-1) + 4*n*(n+7)*a(n-2) + 2*(70*n^2-395*n+564)*a(n-3) + 2*(25*n^2-143*n+222)*a(n-4) + 4*(49*n-228)*(n-5)*a(n-5) - 45*(n-5)*(n-6)*a(n-6) = 0. - _R. J. Mathar_, Mar 14 2014
%F Recurrence (of order 4): 4*n*(n+1)*(91*n^2 - 217*n + 102)*a(n) = 6*n*(182*n^3 - 525*n^2 + 365*n - 78)*a(n-1) - 4*(91*n^4 - 399*n^3 - 136*n^2 + 990*n - 450)*a(n-2) + 12*(n-3)*(182*n^3 - 525*n^2 + 92*n + 140)*a(n-3) - 5*(n-4)*(n-3)*(91*n^2 - 35*n - 24)*a(n-4). - _Vaclav Kotesovec_, Mar 20 2014
%p a:=proc(n) options operator, arrow: (sum(2*binomial(n,2*k)*binomial(n-k,k-1)+n*binomial(n,2*k+1)*binomial(n-k,k)/(n-k),k=0..floor((1/2)*n)))/n end proc: seq(a(n),n=1..27);
%t Table[1/n*Sum[2*Binomial[n,2k]*Binomial[n-k,k-1]+ n*Binomial[n,2k+1] *Binomial[n-k,k]/(n-k),{k,0,n-1}],{n,1,20}] (* _Vaclav Kotesovec_, Mar 20 2014 *)
%K nonn
%O 1,2
%A _Emeric Deutsch_, Jul 17 2008
|
