A023432 Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 3).

1, 1, 1, 1, 2, 4, 7, 12, 22, 42, 80, 152, 292, 568, 1112, 2185, 4313, 8557, 17050, 34089, 68370, 137542, 277475, 561185, 1137595, 2311014, 4704235, 9593662, 19598920, 40103635, 82185653, 168666493, 346613232, 713200114, 1469254621, 3030218948, 6256281188

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

Number of Motzkin paths of length n-1 with no peaks, no double rises and no doubledescents (i.e., no UD's, no UU's and no DD's, where U=(1,1) and D=(1,-1), n>0; can be easily formulated using RNA secondary structure terminology). E.g., a(5)=4 because we have HHHH, HUHD, UHDH and UHHD; here H=(1,0). Also number of peakless Motzkin paths of length n in which each D=(1,-1) step is followed by an H=(1,0) step (can be easily formulated using RNA secondary structure terminology). E.g., a(5)=4 because we have HHHHH, HUHDH, UHDHH and UHHDH (here U=(1,1)). - Emeric Deutsch, Jan 09 2004

The coefficient of t^n in the power series expansion of the solution u in the equation (1-t*u)(u-t*u-t-t^2*u^2+t^3*u)=0. - Shanzhen Gao, May 13 2011

Also the number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 3). The a(5) = 4 paths for n=5 are: UDUDUDUDUD, UUUUDDDDUD, UUUUDUDDDD, UDUUUUDDDD. - Alois P. Heinz, May 09 2012

a(n)=number of strictly alternating bargraphs of semiperimeter n+2. A bargraph is said to be strictly alternating if its ascents and descents alternate and all the formed peaks and valleys have width 1. An ascent (descent) is a maximal sequence of consecutive U (D) steps. Example: a(4) = 2 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only those corresponding to the compositions [5] and [2,1,2] are strictly alternating. - Emeric Deutsch, Aug 26 2016

For n>=1, a(n) is the number of Dyck paths of semilength n+2 in which all ascent and descent lengths are >=3. For example, a(4) = 2 counts U^6.D^6, U^3.D^3.U^3.D^3 where ^ denotes repetition and a dot denotes concatenation. The gf F(x) = 1 + x^3 + x^4 + x^5 + 2*x^6 + ... for these paths satisfies F = 1 + x^3/(1-x) + (F-1)x^3/((1-x)(1-x*F)), which follows from a first return decomposition and summing over the lengths of the first ascent and first descent. A bijection to the title paths would be interesting. - David Callan, Dec 07 2021

Examples

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 12*x^6 + 22*x^7 +...
where the logarithm of the g.f. equals the series:
log(A(x)) = (1 + x^2)*x + (1 + 2^2*x^2 + x^4)*x^2/2 + (1 + 3^2*x^2 + 3^2*x^4 + x^6)*x^3/3 + (1 + 4^2*x^2 + 6^2*x^4 + 4^2*x^6 + x^8)*x^4/4 + (1 + 5^2*x^2 + 10^2*x^4 + 10^2*x^6 + 5^2*x^8 + x^10)*x^5/5 + ... - _Paul D. Hanna_
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
• Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
• A.J. Bu and Robert Dougherty-Bliss, Enumerating restricted Dyck paths with context free grammars, #A69 INTEGERS 21 (2021).
• Emeric Deutsch and S. Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088 [math.CO], 2016.
• S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).
• M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86.

Crossrefs

Cf. A000108, A001006, A004148, A004149, A006318, A082582, A275448.

Column k=3 of A212363.

Programs

Haskell

a023432 n = a023432_list !! n
a023432_list = 1 : 1 : f [1,1] where
   f xs'@(x:_:xs) = y : f (y : xs') where
     y = x + sum (zipWith (*) xs $ reverse $ tail xs)
-- Reinhard Zumkeller, Nov 13 2012

Maple

a:= proc(n) option remember;
      `if`(n=0, 1, a(n-1) +add(a(k)*a(n-3-k), k=1..n-3))
    end:
seq(a(n), n=0..50); # Alois P. Heinz, May 09 2012

Mathematica

Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-3-k ], {k, 0, n-4} ];
CoefficientList[Series[(1-x+x^3-Sqrt[1-2*x-2*x^3+x^2-2*x^4+x^6])/(2*x^3), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 22 2014 *)

Maxima

a(n):=if n=0 then 1 else sum(binomial(n-2*q,q)*binomial(n-2*q,q+1)/(n-2*q),q,0,(n-1)/2); /* Vladimir Kruchinin, Jan 21 2019 */

PARI

{a(n)=local(A=1+x);for(i=1,n,A=(1+x*A)*(1+x^3*A +x*O(x^n)));polcoeff(A, n)} /* Paul D. Hanna */

PARI

{a(n)=polcoeff( exp(sum(m=1, n+1, x^m/m*sum(j=0, m, binomial(m, j)^2*x^(2*j))+x*O(x^n))), n)} /* Paul D. Hanna */

PARI

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (1-x^2)^(2*m+1)*sum(j=0, n\2, binomial(m+j, j)^2*x^(2*j))*x^m/m)+x*O(x^n))); polcoeff(A, n, x)} /* Paul D. Hanna */

Formula

G.f.: (1-z+z^3-sqrt(1-2z-2z^3+z^2-2z^4+z^6))/(2z^3). - Emeric Deutsch, Jan 09 2004

G.f.: 1/(1-x-x^4/(1-x-x^3-x^4/(1-x-x^3-x^4/(1-x-x^3-x^4/(1-... (continued fraction). - Paul Barry, May 22 2009

G.f.: 1/(1-x/(1-x^3/(1-x/(1-x^3/(1-x/(1-x^3/(1-... (continued fraction). - Paul Barry, Nov 30 2009

From Paul D. Hanna, Nov 01 2011: (Start)

G.f. (for offset -1) satisfies: A(x) = (1 + x*A(x))*(1 + x^3*A(x)).

G.f.: A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * x^(2*k) ).

G.f.: A(x) = exp( Sum_{n>=1} x^n/n * (1-x^2)^(2*n+1) * Sum_{k>=0} C(n+k,k)^2 * x^(2*k) ). (End)

a(n) ~ sqrt(3-5*r+2*r^2-3*r^3-2*r^4) / (2*sqrt(2*Pi)*n^(3/2)*r^(n+3)), where r = 0.465571231876768... is the root of the equation 1+r^2+r^6 = 2*r*(1+r^2+r^3). - Vaclav Kotesovec, Mar 22 2014

a(n) = Sum_{k=0..(n-1)/2} C(n-2*k,k)*C(n-2*k,k+1)/(n-2*k), n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019

D-finite with recurrence (n+3)*a(n) +(-2*n-3)*a(n-1) +n*a(n-2) +(-2*n+3)*a(n-3) +2*(-n+3)*a(n-4) +(n-6)*a(n-6)=0. - R. J. Mathar, Jul 23 2023

Extensions

New name, using a comment of Alois P. Heinz, from Peter Luschny, Jan 21 2019