A143017 Number of {2-1-3, 2'^e-31}-avoiding permutations of size n (see definition in the Elizalde paper).
1, 2, 4, 9, 22, 56, 147, 396, 1088, 3036, 8582, 24524, 70727, 205594, 601756, 1771937, 5245544, 15602496, 46606356, 139753120, 420520000, 1269361000, 3842722454, 11663928644, 35490451807, 108232655126, 330760284892
Offset: 1
Keywords
Links
- David Callan, Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS
- S. Elizalde, Generating trees for permutations avoiding generalized patterns, arXiv:0707.4633 [math.CO], 2007; Annals of Combinatorics 11 (2007), 435-458.
- Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.
Programs
-
Maple
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);
-
Mathematica
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 *)
Formula
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).
G.f. G(x) satisfies x*G^3 + (4x-2)*G^2 + (4x-1)*G + x = 0.
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
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
Comments