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

%I #40 Jan 01 2024 02:14:53

%S 1,1,1,2,3,6,10,21,37,80,146,322,602,1347,2563,5798,11181,25512,49720,

%T 114236,224540,518848,1027038,2384538,4748042,11068567,22150519,

%U 51817118,104146733,244370806,493012682,1159883685,2347796965,5536508864,11239697816,26560581688,54061835288

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

%C This sequence interleaves the counts of the closely related sequences A109081 and A106228.

%C 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 Alois P. Heinz, <a href="/A215067/b215067.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1);

%F a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).

%F 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 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 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 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 a(5) = 6: fUfFd, fUfDf, fUdUd, fUdFf, fFfUd, fFfFf showing odd-numbered steps in lower case.

%p b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,

%p `if`(x=0, 1, b(x-1, y) +b(x-1, y+1) +

%p `if`(irem(x, 2)=1, 0, b(x-1, y-1)) ))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Apr 04 2013

%t 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 (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 (Sage)

%o from mpmath import mp

%o mp.dps = 25; mp.pretty = True

%o def A215067(n) :

%o m = n%2; r = n//2 if n>0 else 1

%o return r^(1-m)*mp.hyper([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)

%o [int(A215067(i)) for i in (0..32)] # _Peter Luschny_, Aug 03 2012

%Y Cf. A109081, A106228, A114465.

%K nonn

%O 0,4

%A _David Scambler_, Aug 02 2012