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

%I

%S 1,1,1,1,2,4,7,12,22,42,80,152,292,568,1112,2185,4313,8557,17050,

%T 34089,68370,137542,277475,561185,1137595,2311014,4704235,9593662,

%U 19598920,40103635,82185653,168666493,346613232,713200114,1469254621,3030218948,6256281188

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

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

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

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

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

%H Alois P. Heinz, <a href="/A023432/b023432.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

%H Andrei Asinowski, Cyril Banderier, Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).

%H Emeric Deutsch, S Elizalde, <a href="http://arxiv.org/abs/1609.00088">Statistics on bargraphs viewed as cornerless Motzkin paths</a>, arXiv preprint arXiv:1609.00088 [math.CO], 2016.

%H S. Gao, H. Niederhausen, <a href="http://math.fau.edu/Niederhausen/HTML/Papers/Sequences%20Arising%20From%20Prudent%20Self-Avoiding%20Walks-February%2001-2010.pdf">Sequences Arising From Prudent Self-Avoiding Walks</a>, (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86.

%F G.f.: (1-z+z^3-sqrt(1-2z-2z^3+z^2-2z^4+z^6))/(2z^3). - _Emeric Deutsch_, Jan 09 2004

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

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

%F From _Paul D. Hanna_, Nov 01 2011: (Start)

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

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

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

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

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

%e G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 12*x^6 + 22*x^7 +...

%e where the logarithm of the g.f. equals the series:

%e 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_

%p a:= proc(n) option remember;

%p `if`(n=0, 1, a(n-1) +add(a(k)*a(n-3-k), k=1..n-3))

%p end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, May 09 2012

%t Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-3-k ], {k, 0, n-4} ];

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

%o (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_ */

%o (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_ */

%o (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_ */

%o (Haskell)

%o a023432 n = a023432_list !! n

%o a023432_list = 1 : 1 : f [1,1] where

%o f xs'@(x:_:xs) = y : f (y : xs') where

%o y = x + sum (zipWith (*) xs $ reverse $ tail xs)

%o -- _Reinhard Zumkeller_, Nov 13 2012

%o (Maxima)

%o 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 */

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

%Y Column k=3 of A212363.

%K nonn,easy

%O 0,5

%A _Olivier Gérard_

%E New name, using a comment of _Alois P. Heinz_, from _Peter Luschny_, Jan 21 2019

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 September 29 12:15 EDT 2020. Contains 337431 sequences. (Running on oeis4.)