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

%I M3521 #116 Jul 31 2024 09:07:49

%S 1,1,4,16,68,304,1412,6752,33028,164512,831620,4255728,22004292,

%T 114781008,603308292,3192216000,16989553668,90890869312,488500827908,

%U 2636405463248,14281895003716,77631035881072,423282220216964,2314491475510816,12688544297945348

%N Royal paths in a lattice (convolution of A006318).

%C 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

%C 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

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

%H T. D. Noe, <a href="/A006319/b006319.txt">Table of n, a(n) for n = 0..200</a>

%H Axel Bacher, <a href="http://arxiv.org/abs/1301.1365">Directed and multi-directed animals on the square lattice with next nearest neighbor edges</a>, arXiv preprint arXiv:1301.1365 [math.CO], 2013. See Q(t). - _N. J. A. Sloane_, Feb 14 2013

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry3/barry93.html">Continued fractions and transformations of integer sequences</a>, JIS 12 (2009) 09.7.6.

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 19.

%H G. Kreweras, <a href="http://www.numdam.org/item?id=BURO_1973__20__3_0">Sur les hiérarchies de segments</a>, Cahiers Bureau Universitaire Recherche Opérationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.

%H G. Kreweras, <a href="/A001844/a001844.pdf">Sur les hiérarchies de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)

%H G. Kreweras, <a href="/A006318/a006318_2.pdf">Aires des chemins surdiagonaux et application à un problème économique</a>, Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche 24 (1976): 1-8. [Annotated scanned copy]

%H Emanuele Munarini, <a href="http://www.emis.de/journals/INTEGERS/papers/j29/j29.Abstract.html">Combinatorial properties of the antichains of a garland</a>, Integers, 9 (2009), 353-374.

%H Luis Verde-Star, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Verde/verde4.html">A Matrix Approach to Generalized Delannoy and Schröder Arrays</a>, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.

%H Sai-nan Zheng and Sheng-liang Yang, <a href="http://dx.doi.org/10.1155/2014/848374">On the-Shifted Central Coefficients of Riordan Matrices</a>, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

%F 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

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

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

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

%F a(n) = 0^n + Sum_{k=0..n-1} binomial(n+k, 2*k+1)*A000108(k+1). - _Paul Barry_, Feb 01 2009

%F 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

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

%F 2, 2, 0, 0, 0, 0, ...

%F 1, 1, 2, 0, 0, 0, ...

%F 1, 1, 1, 2, 0, 0, ...

%F 1, 1, 1, 1, 2, 0, ...

%F 1, 1, 1, 1, 1, 2, ...

%F ... - _Gary W. Adamson_, Aug 23 2011

%F a(n) ~ 2^(1/4)*(3+2*sqrt(2))^n/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 09 2013

%F 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

%F 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

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

%F From _Peter Bala_, Jan 28 2020: (Start)

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

%F (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.

%F 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)

%F a(n) = 0^n + n*hypergeom([1 - n, n + 1], [3], -1). - _Peter Luschny_, Jan 31 2020

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

%t 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}]

%t a[0] := 1; a[n_] := n Hypergeometric2F1[1 - n, n + 1, 3, -1];

%t Array[a, 25, 0] (* _Peter Luschny_, Jan 31 2020 *)

%o (Sage)

%o def A006319_list(n) :

%o D = [0]*(n+1); D[1] = 1

%o b = True; h = 2; R = [1]

%o for i in range(2*n-2) :

%o if b :

%o for k in range(h,0,-1) : D[k] += D[k-1]

%o h += 1;

%o else :

%o for k in range(1,h, 1) : D[k] += D[k-1]

%o R.append(D[h-2]);

%o b = not b

%o return R

%o A006319_list(25) # _Peter Luschny_, Jun 03 2012

%o (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

%o (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

%Y First differences of A006318. Second diagonal of A033877.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_