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!)
A023432 Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 3). 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Andrei Asinowski, Axel Bacher, Cyril Banderier, 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, Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).

Emeric Deutsch, S Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088 [math.CO], 2016.

S. Gao, 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.

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

EXAMPLE

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

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

PROG

(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 */

(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

(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 */

CROSSREFS

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

Column k=3 of A212363.

Sequence in context: A018179 A190165 A127542 * A072641 A280352 A135360

Adjacent sequences:  A023429 A023430 A023431 * A023433 A023434 A023435

KEYWORD

nonn,easy

AUTHOR

Olivier Gérard

EXTENSIONS

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

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 August 3 10:49 EDT 2020. Contains 336198 sequences. (Running on oeis4.)