A071359 Expansion of (1-x-sqrt(1-2*x-3*x^2-4*x^3))/(2*x*(1+x)).

0, 1, 1, 2, 5, 12, 31, 83, 227, 634, 1799, 5171, 15027, 44074, 130299, 387880, 1161665, 3497734, 10581819, 32150411, 98057835, 300116888, 921456715, 2837379238, 8760199757, 27112737988, 84103586027, 261435982873, 814257033047

Offset

0,4

Comments

a(n) counts Horse permutations of length n-1 (see Hou and Mansour reference, Proposition 3.1). - David Callan, Aug 27 2014

Links

Table of n, a(n) for n=0..28.

Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.

D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

Q. Hou and T. Mansour, Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials, Discrete Applied Mathematics 154:8 (2006) 1183-1197.

Formula

a(n+1) = sum(k=0..n/2, binomial(2*k,k)/(k+1) * sum(i=0..k, binomial(k,i)*binomial(n-i,2*k) ) ).

D-finite with recurrence: (for b(n)=a(n+1)): 0 = 2*(n^2+14*n+48)*b(n+6) + (n^2+11*n+24)*b(n+5) - 2*(7*n^2+74*n+198)*b(n+4) - 2*(14*n^2+133*n+309)*b(n+3) - 6*(4*n^2+33*n+66)*b(n+2) - (5*n^2+49*n+90)*b(n+1) + 2*(2*n^2+7*n+6)*b(n). [Emanuele Munarini, May 06 2011]

a(0)=0, a(1)=1, a(2)=1, a(3)=2, a(n) = ((n-2)*a(n-1) +(5*n-7)*a(n-2) +(7*n-20) *a(n-3) +(4*n-14)*a(n-4))/(n+1). - Tani Akinari, Jul 03 2013

Mathematica

Table[Sum[Binomial[2k, k]/(k+1)Sum[Binomial[k, i]Binomial[n-i, 2k], {i, 0, k}], {k, 0, n/2}], {n, 0, 29}] (* for a(n+1) *) (* Emanuele Munarini, May 06 2011 *)

Prog

(Maxima) makelist(sum(binomial(2*k, k)/(k+1)*sum(binomial(k, i)*binomial(n-i, 2*k), i, 0, k), k, 0, n/2), n, 0, 29); (* for a(n+1) *) [Emanuele Munarini, May 06 2011]

Crossrefs

Sequence in context: A097893 A093379 A271929 * A160999 A014329 A045633

Adjacent sequences: A071356 A071357 A071358 * A071360 A071361 A071362

Keyword

nonn

Author

N. J. A. Sloane, Jun 12 2002

Status

approved