login
This site is supported by donations to The OEIS 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

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 November 11 18:50 EST 2019. Contains 329031 sequences. (Running on oeis4.)