|
%I #95 Jul 23 2023 13:29:08
%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
%C 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
%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, and 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, and 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 A.J. Bu and Robert Dougherty-Bliss, <a href="http://math.colgate.edu/~integers/v69/v69.mail.html">Enumerating restricted Dyck paths with context free grammars</a>, #A69 INTEGERS 21 (2021).
%H Emeric Deutsch and 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 and 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
%F 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
%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
|
