A096794 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.

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, 186, 260, 264, 240, 160, 192, 0, 128, 622, 864, 880, 768, 640, 384, 448, 0, 256, 2120, 2932, 2976, 2624, 2080, 1632, 896, 1024, 0, 512, 7338, 10112, 10248, 9024, 7280

Offset

1,3

Comments

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.

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

Links

Table of n, a(n) for n=1..60.

Formula

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.

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

Example

Table begins
\ k 0, 1, 2, ...
n
1 | 1
2 | 0, 2
3 | 1, 0, 4
4 | 2, 4, 0, 8
5 | 6, 8, 12, 0, 16
6 | 18, 26, 24, 32, 0, 32
7 | 57, 80, 84, 64, 80, 0, 64
a(4,1) = 4 because UudUUDDD, UUUDDudD, UduUUDDD, UUUDDduD each contain one relevant turn (in small type).

Prog

(Maxima)
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 */

Crossrefs

Row sums are the Catalan numbers A000108.

Sequence in context: A004558 A129699 A002349 * A106375 A194734 A255528

Adjacent sequences: A096791 A096792 A096793 * A096795 A096796 A096797

Keyword

nonn,tabl

Author

David Callan, Aug 17 2004

Status

approved