login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006319 Royal paths in a lattice (convolution of A006318).
(Formerly M3521)
17
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 (list; graph; refs; listen; history; text; internal format)
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

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

A. 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

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

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.

S.-n. Zheng and S.-l. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 24 18:46 EST 2021. Contains 341584 sequences. (Running on oeis4.)