[seqfan] Re: Motzkin n-paths avoiding even-numbered steps that are up steps.

[Paul D Hanna]

Dave, 
    That is interesting.  Below are some formulas.  
(1)  
G.f. satisfies: A(x) = G(x*A(x)) where G(x) = (3+2*x+x^2 + sqrt((1+x^2)*(1+4*x+x^2)))/4. 
 
Note that G(x) = 1+x+x^2 - x*F(-x) where F(x) is the g.f. of A159771, which is the number of n-leaf binary trees that do not contain (()((()())((()())()))) as a subtree. 
 
(2) Also, we have the binomial sums:  
 
a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1); 
a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).  
  
Paul 
 
---------- Original Message ----------
From: David Scambler <dscambler at bmm.com>
To: "seqfan at list.seqfan.eu" <seqfan at list.seqfan.eu>
Subject: [seqfan] Motzkin n-paths avoiding even-numbered steps that are up steps.
Date: Thu, 2 Aug 2012 01:25:00 +0000

Seqfans,

This is interesting because the counts are the interleaving of the closely related sequences 
A109081 and A106228.

http://oeis.org/search?q=A106228|A109081&sort=&language=english&go=Search


1,1,1,2,3,6,10,21,37,80,146,322,602,1347,2563,5798,11181,25512,49720,114236,224540,518848,
1027038,2384538,4748042,11068567,22150519,51817118,104146733,244370806,493012682,1159883685,
2347796965,5536508864,11239697816,26560581688,54061835288,127993221140,261130778516,
619280193640,1266125122956,3007251366000,6160158505040,14651743202152,30065608532008,
71601107803904,147161532388934

MMA:
f[n_,x_,y_]:=f[n,x,y] = If[x>n||y<0,0,If[x==n&&y==0,1, If[EvenQ[x],0,
If[y>n-x-1,0,f[n,x+1,y+1]]] +If[y<=0,0,f[n,x+1,y-1]] + f[n,x+1,y]]];
Table[f[n,0,0],{n,0,46}]

dave

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/