A064641 Unidirectional 'Delannoy' variation of the Boustrophedon transform applied to all 1's sequence: construct an array in which the first element of each row is 1 and subsequent entries are given by T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k) + T(n-2,k-1). The last number in row n gives a(n).

1, 2, 7, 29, 133, 650, 3319, 17498, 94525, 520508, 2910895, 16487795, 94393105, 545337200, 3175320607, 18615098837, 109783526821, 650884962908, 3877184797783, 23193307022861, 139271612505361, 839192166392276, 5072534905324615, 30749397292689194

Offset: 0

Author

Floor van Lamoen, Oct 03 2001

Keywords

• nonn

Comments

Also the number of paths from (0,0) to (n,n) not rising above y=x, using steps (1,0), (0,1), (1,1) and (2,1). For example, the 7 paths to (2,2) are dd, den, end, enen, Dn, eenn and edn, where e=(1,0), n=(0,1), d=(1,1) and D=(2,1). - Brian Drake, Aug 01 2007

For another interpretation as the number of walks of a certain type, see A223092 and the link below. - N. J. A. Sloane, Mar 29 2013

Hankel transform is 3^C(n+1,2). - Paul Barry, Jan 26 2009

Examples

			The array begins
        1
      1   2
    1   5   7
  1   8  22  29
G.f. = 1 + 2*x + 7*x^3 + 29*x^4 + 133*x^5 + 650*x^6 + 3319*x^7 + ...
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
• Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
• Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
• Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
• P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
• Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
• M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, Volume 30, Issue 6, pp 1427-1452.
• M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
• N. J. A. Sloane, Illustration of initial terms of A223092 and A064641
• D. V. Kruchinin, On solving some functional equations, Advances in Difference Equations (2015) 2015:17; DOI 10.1186/s13662-014-0347-9.
• Index entries for sequences related to boustrophedon transform

Crossrefs

Delannoy numbers: A008288, table: A064642. Cf. A038764, A223092.

Row sums of A201159.

Programs

Maple

A:= series( (1-x-sqrt(1-6*x-3*x^2)) / (2*x*(1+x)),x, 21): seq(coeff(A,x,i), i=0..20); # Brian Drake, Aug 01 2007

Mathematica

Table[SeriesCoefficient[(1-x-Sqrt[1-6*x-3*x^2])/(2*x*(1+x)),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 13 2012 *)

Maxima

a(n):=sum(binomial(n+i,n)*sum(binomial(j,-n+2*j-i-2)*binomial(n+1,j),j,0,n+1),i,0,n)/(n+1); /* Vladimir Kruchinin, May 12 2011 */

PARI

a(n)=if(n<0,0,polcoeff(serreverse(x*(1-x)/(1+x+x^2)+O(x^(n+2))),n+1)) /* Paul Barry */

Formula

G.f.: (1-x-sqrt(1-6x-3x^2)) / (2x(1+x)). - Brian Drake, Aug 01 2007

G.f.: 1/(1-2x-3x^2/(1-3x-3x^2/(1-3x-3x^2/(1-3x-3x^2/(1-.... (continued fraction). - Paul Barry, Jan 26 2009

a(n) = sum(i=0..n, binomial(n+i,n)*sum(j=0..n+1, binomial(j,-n+2*j-i-2)*binomial(n+1,j)))/(n+1). - Vladimir Kruchinin, May 12 2011

Recurrence: (n+1)*a(n) = (5*n-4)*a(n-1) + 9*(n-1)*a(n-2) + 3*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 13 2012

a(n) ~ 3*(sqrt(6)+sqrt(2))*(3+2*sqrt(3))^n/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 13 2012

G.f.: 1 / (1 - x - (x+x^2) / (1 - x - (x+x^2) / ... )) (continued fraction). - Michael Somos, Mar 30 2014

0 = a(n)*(+9*a(n+1) + 54*a(n+2) + 33*a(n+3) - 12*a(n+4)) + a(n+1)*(+78*a(n+2) + 60*a(n+3) - 27*a(n+4)) + a(n+2)*(+36*a(n+2) + 34*a(n+3) - 14*a(n+4)) + a(n+3)*(+4*a(n+3) + a(n+4)) for all n >= 0. - Michael Somos, Nov 05 2014

a(n) = (-1)^n * (n+1) + Sum_{k=0..n-1} (a(k) + (-1)^k) * (a(n-1-k) + (-1)^(n-1-k)). - Seiichi Manyama, Jul 18 2025