A006319 Royal paths in a lattice (convolution of A006318). (Formerly M3521)

1, 1, 4, 16, 68, 304, 1412, 6752, 33028, 164512, 831620, 4255728, 22004292, 114781008, 603308292, 3192216000, 16989553668, 90890869312, 488500827908, 2636405463248, 14281895003716, 77631035881072, 423282220216964, 2314491475510816, 12688544297945348

Offset

0,3

Comments

Number of peaks at level 1 in all Schröder paths of semilength n (n>=1). Example: a(2)=4 because in the six Schröder paths of semilength two, HH, H(UD), (UD)H, (UD)(UD), UHD and UUDD (where H=(2,0), U=(1,1), D=(1,-1)), we have four peaks at level 1 (shown between parentheses). - Emeric Deutsch, Dec 27 2003

a(n) = number of Schroder n-paths (subdiagonal paths of steps E = (1,0), N = (0,1), and D = (1,1) from the origin to (n,n) ) that start with an E step. For example, a(2) = 4 counts END, ENEN, EDN, EENN. - David Callan, May 15 2022

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n = 0..200

Axel Bacher, Directed and multi-directed animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365 [math.CO], 2013. See Q(t). - N. J. A. Sloane, Feb 14 2013

Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.

Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 19.

G. Kreweras, Sur les hiérarchies de segments, Cahiers Bureau Universitaire Recherche Opérationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.

G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)

G. Kreweras, Aires des chemins surdiagonaux et application à un problème économique, Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche 24 (1976): 1-8. [Annotated scanned copy]

Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.

Luis Verde-Star A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.

Sai-nan Zheng and Sheng-liang Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

Formula

All listed terms satisfy the recurrence a(1) = 1 and, for n > 1, a(n) = 4*a(n-1) + Sum_{k=2..n-2} a(k)*a(n-k-1). - John W. Layman, Feb 23 2001

From Mario Catalani (mario.catalani(AT)unito.it), Jun 19 2003: (Start)

a(n) = Sum_{j=0..n} (n-j)*(Sum_{i=0..j} a(i)*a(j-i)) for n > 0, a(0)=1.

G.f.: A(x) = (1/(2x))((1-x)^2 - sqrt((1-x)^4 - 4*x*(1-x)^2)) (End)

a(n) = 0^n + Sum_{k=0..n-1} binomial(n+k, 2*k+1)*A000108(k+1). - Paul Barry, Feb 01 2009

G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z = x/(1-x)^2 (continued fraction); more generally g.f. C(x/(1-x)^2) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011

a(n) is the sum of top row terms in M^(n-1), M = an infinite square production matrix as follows:

2, 2, 0, 0, 0, 0, ...

1, 1, 2, 0, 0, 0, ...

1, 1, 1, 2, 0, 0, ...

1, 1, 1, 1, 2, 0, ...

1, 1, 1, 1, 1, 2, ...

... - Gary W. Adamson, Aug 23 2011

a(n) ~ 2^(1/4)*(3+2*sqrt(2))^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013

D-finite with recurrence: (n+1)*a(n) + (-7*n+4)*a(n-1) + (7*n-17)*a(n-2) + (-n+4)*a(n-3) = 0. - R. J. Mathar, Oct 16 2013

a(n) = Sum_{k=0..n} (2/(k+2))*binomial(n+k,k+1)*binomial(n-1,k) for n >= 1. - David Callan, Jul 21 2017

G.f. A(x) satisfies: A(x) = 1/(1 - Sum_{k>=1} k*x^k*A(x)). - Ilya Gutkovskiy, Apr 10 2018

From Peter Bala, Jan 28 2020: (Start)

a(n) = A006318(n) - A006318(n-1) for n >= 1.

(2*n-3)*(n+1)*a(n) = 12*(n-1)^2*a(n-1) - (2*n-1)*(n-3)*a(n-2) with a(1) = 1, a(2) = 4.

O.g.f. A(x) = (1 - x)*( (1 - x) - sqrt(1 - 6*x + x^2) )/(2*x) = (1 - x)*S(x) = 1 + x*S(x)^2, where S(x) is the o.g.f. for the large Schröder numbers A006318. (End)

a(n) = 0^n + n*hypergeom([1 - n, n + 1], [3], -1). - Peter Luschny, Jan 31 2020

Example

a(4) = 68 since the top row of M^3 = (22, 22, 16, 8, 0, 0, 0, ...); where 68 = (22 + 22 + 16 + 8).

Mathematica

d[n_] := d[n] = Sum[(n - j)*Sum[d[i]d[j - i], {i, 0, j}], {j, 0, n-1}]; d[0] = 1; Table[d[n], {n, 0, 26}]
a[0] := 1; a[n_] := n Hypergeometric2F1[1 - n, n + 1, 3, -1];
Array[a, 25, 0] (* Peter Luschny, Jan 31 2020 *)

Prog

(Sage)
def A006319_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 2; R = [1]
    for i in range(2*n-2) :
        if b :
            for k in range(h, 0, -1) : D[k] += D[k-1]
            h += 1;
        else :
            for k in range(1, h, 1) : D[k] += D[k-1]
            R.append(D[h-2]);
        b = not b
    return R
A006319_list(25) # Peter Luschny, Jun 03 2012
(Magma) [1] cat [&+[2/(k+2)*Binomial(n+k, k+1)*Binomial(n-1, k): k in [0..n]]: n in [1..25]]; // Vincenzo Librandi, Jul 22 2017
(PARI) apply( {A006319(n)=!n+sum(k=0, n-1, binomial(n+k, k+1)*binomial(n-1, k)*2/(k+2))}, [0..30]) \\ M. F. Hasler, Jan 29 2020

Crossrefs

First differences of A006318. Second diagonal of A033877.

Sequence in context: A179191 A128730 A151243 * A202020 A059606 A228950

Adjacent sequences: A006316 A006317 A006318 * A006320 A006321 A006322

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved