cp's OEIS Frontend

A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.

%I A215067 #43 Feb 20 2025 05:04:07
%S A215067 1,1,1,2,3,6,10,21,37,80,146,322,602,1347,2563,5798,11181,25512,49720,
%T A215067 114236,224540,518848,1027038,2384538,4748042,11068567,22150519,
%U A215067 51817118,104146733,244370806,493012682,1159883685,2347796965,5536508864,11239697816,26560581688,54061835288
%N A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.
%C A215067 This sequence interleaves the counts of the closely related sequences A109081 and A106228.
%C A215067 a(n) is the number of (peakless) Motzkin paths of length n where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on n vertices where only vertices of the same parity can be matched. - _Alexander Burstein_, May 17 2021
%H A215067 Alois P. Heinz, <a href="/A215067/b215067.txt">Table of n, a(n) for n = 0..1000</a>
%H A215067 Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%F A215067 a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1);
%F A215067 a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).
%F A215067 G.f.: (1/x)*Series_Reversion( x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)))/(2*(1+x+x^2)) ). - _Paul D. Hanna_, Aug 02 2012
%F A215067 G.f. satisfies: A(x) = G(x*A(x)) where G(x) = A(x/G(x)) = (3+2*x+x^2 + sqrt((1+x^2)*(1+4*x+x^2)))/4. - _Paul D. Hanna_, Aug 02 2012
%F A215067 G.f. satisfies: Series_Reversion(x*A(x)) = x - x^2*F(-x) where F(x) = g.f. of A114465. - _Paul D. Hanna_, Aug 02 2012
%F A215067 a(n) = 3_F_2([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)*r^(1-m) for n>0 where m = n mod 2 and r = floor(n/2). - _Peter Luschny_, Aug 03 2012
%e A215067 a(5) = 6: fUfFd, fUfDf, fUdUd, fUdFf, fFfUd, fFfFf showing odd-numbered steps in lower case.
%p A215067 b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
%p A215067       `if`(x=0, 1, b(x-1, y) +b(x-1, y+1) +
%p A215067       `if`(irem(x, 2)=1, 0, b(x-1, y-1)) ))
%p A215067     end:
%p A215067 a:= n-> b(n, 0):
%p A215067 seq(a(n), n=0..40);  # _Alois P. Heinz_, Apr 04 2013
%t A215067 f[n_,x_,y_]:=f[n,x,y] = If[x>n||y<0,0,If[x==n&&y==0,1, If[EvenQ[x],0,f[n,x+1,y+1]] +f[n,x+1,y-1] + f[n,x+1,y]]]; Table[f[n,0,0],{n,0,35}]
%o A215067 (PARI) {a(n)=polcoeff((1/x)*serreverse(x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)+x^2*O(x^n)))/(2*(1+x+x^2+x^2*O(x^n)))),n)} \\ _Paul D. Hanna_, Aug 02 2012
%o A215067 (Sage)
%o A215067 from mpmath import mp
%o A215067 mp.dps = 25; mp.pretty = True
%o A215067 def A215067(n) :
%o A215067     m = n%2; r = n//2 if n>0 else 1
%o A215067     return r^(1-m)*mp.hyper([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)
%o A215067 [int(A215067(i)) for i in (0..32)]  # _Peter Luschny_, Aug 03 2012
%Y A215067 Cf. A109081, A106228, A114465, A084075.
%K A215067 nonn
%O A215067 0,4
%A A215067 _David Scambler_, Aug 02 2012