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,2

Comments

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

Links

Table of n, a(n) for n=1..27.

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.

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

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 *)

Crossrefs

Sequence in context: A152225 A037245 A244886 * A307575 A301362 A130018

Adjacent sequences: A143014 A143015 A143016 * A143018 A143019 A143020

Keyword

nonn

Author

Emeric Deutsch, Jul 17 2008

Status

approved