login
Triangle read by rows: a(n,k) = number of Dyck n-paths such that number of DUs at level 1 plus number of UDs at level 2 is k, 0<=k<=n-1.
0

%I #19 Mar 07 2016 12:41:17

%S 1,0,2,1,0,4,2,4,0,8,6,8,12,0,16,18,26,24,32,0,32,57,80,84,64,80,0,64,

%T 186,260,264,240,160,192,0,128,622,864,880,768,640,384,448,0,256,2120,

%U 2932,2976,2624,2080,1632,896,1024,0,512,7338,10112,10248,9024,7280

%N Triangle read by rows: a(n,k) = number of Dyck n-paths such that number of DUs at level 1 plus number of UDs at level 2 is k, 0<=k<=n-1.

%C Column k has g.f. F(x)^(k+1)*(2y)^k where F(x)=(1-sqrt(1-4*x))/(3-sqrt(1-4*x)) is the g.f. for Fine's sequence A000957.

%C a(n,k) = number of 2-Motzkin paths (i.e. Motzkin paths with blue and red level steps) of length n-1 such that the number of level steps at level 0 is k. Example: a(4,1) = 4 because we have BUD, RUD, UDB, and UDR, where U = (1,1), D = (1,-1), B = blue (1,0), and R = red (1,0). - _Emeric Deutsch_, Sep 15 2014

%F G.f.: (1 - (1 - 4*x)^(1/2))/(3 - 2y + (2y-1)(1 - 4*x)^(1/2) ) = Sum_{n>=1, k>=0} a(n, k) x^n y^k.

%F T(n,m) = (2^(m-1)*Sum_{k=0..n-m}((k+m)*binomial(k+m-1,k)*(-1)^(k)*binomial(2*n-k-m-1,n-k-m)))/n. - _Vladimir Kruchinin_, Mar 07 2016

%e Table begins

%e \ k 0, 1, 2, ...

%e n

%e 1 | 1

%e 2 | 0, 2

%e 3 | 1, 0, 4

%e 4 | 2, 4, 0, 8

%e 5 | 6, 8, 12, 0, 16

%e 6 | 18, 26, 24, 32, 0, 32

%e 7 | 57, 80, 84, 64, 80, 0, 64

%e a(4,1) = 4 because UudUUDDD, UUUDDudD, UduUUDDD, UUUDDduD each contain one relevant turn (in small type).

%o (Maxima)

%o T(n,m):=(2^(m-1)*sum((k+m)*binomial(k+m-1,k)*(-1)^(k)*binomial(2*n-k-m-1,n-k-m),k,0,n-m))/n; /* _Vladimir Kruchinin_, Mar 07 2016 */

%Y Row sums are the Catalan numbers A000108.

%K nonn,tabl

%O 1,3

%A _David Callan_, Aug 17 2004