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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Examples

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

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.

Crossrefs

First differences of A006318. Second diagonal of A033877.

Programs

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

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

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

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

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