A087647 Triangle of 3-Narayana numbers, N(n,k), for n >= 1, 0 <= k <= 2n-2.

1, 1, 3, 1, 1, 10, 20, 10, 1, 1, 22, 113, 190, 113, 22, 1, 1, 40, 400, 1456, 2212, 1456, 400, 40, 1, 1, 65, 1095, 7095, 20760, 29484, 20760, 7095, 1095, 65, 1, 1, 98, 2541, 26180, 127435, 320034, 433092, 320034, 127435, 26180, 2541, 98, 1, 1, 140, 5250, 79870

Offset: 1

Author

Robert A. Sulanke (sulanke(AT)math.boisestate.edu), Sep 23 2003

Keywords

• easy
• nonn
• tabf

Comments

N(n,k) counts ballot sequences for three candidates having length 3n, ending in a tie and having k instances of a vote for a weaker candidate being followed immediately by a vote for a stronger one.

Equivalently, N(n,k) counts the lattice paths P := p_1p_2...p_{3n} using the steps X := (1,0,0), Y := (0,1,0) and Z := (0,0,1), running from (0,0,0) to (n,n,n), lying in {(x,y,z) : 0<=x<=y<=z } and satisfying #{i : p_ip_{i+1} in {XY,XZ,YZ} } = k.

Examples

			1;
1,3,1;
1,10,20,10,1;
1,22,113,190,113,22,1;
1,40,400,1456,2212,1456,400,40,1;
1,65,1095,7095,20760,29484,20760,7095,1095,65,1;
1,98,2541,26180,127435,320034,433092,320034,127435,26180,2541,98,1
		

Links

• Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
• R. A. Sulanke, Counting Lattice Paths by Narayana Polynomials Electronic J. Combinatorics 7, No. 1, R40, 1-9, 2000.
• R. A. Sulanke, Generalizing Narayana and Schroeder Numbers to Higher Dimensions, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp.
• R. A. Sulanke, Three-dimensional Narayana and Schröder numbers, Theoretical Computer Science, Volume 346, Issues 2-3, 28 November 2005, Pages 455-468.

Crossrefs

Cf. A001263 (Narayana numbers), A005789 (= Sum[N(n, k), {k, 0, 2n-2}], 3-dimensional Catalan numbers), A056939 (antichains in the poset 3*m*n).

Programs

Maple

seq( seq( add(2*(-1)^(k-j)*binomial(3*n+1, k-j)* binomial(n+j,n)*binomial(n+j+1,n)*binomial(n+j+2,n)/(n+1)^2/(n+2), j = 0 .. k), k = 0 .. 2*n-2), n = 1 ..7 );

Formula

For 0<=k<=2n-2, N(n, k) := Sum[2*(-1)^(k-j)*C(3*n+1, k-j)*C(n+j, n)*C(n+j+1, n)*C(n+j+2, n)/(n+1)^2/(n+2), {j, 0, k}] = Sum[(-1)^(k-j)*C(3*n+1, k-j)*a(n, j), {j, 0, k}] where a(m, n) is an entry in the triangle of A056939.

Recurrence: If N_n(t) := Sum[t^k*N(n, k), {k, 0, 2n-2}] then (3n-4)(n+2)(n+1)^2 N_n(t) = (3n-2)(n+1)( 4(1+t+t^2) - 5(1+7t+t^2)n +3(1+7t+t^2)n^2 ) N_{n-1}(t) - (n-2)( -12 +29n -30n^2 +9n^3)(1-t)^4 N_{n-2}(t) +(3n-1)(n-2)(n-3)(n-4) (1-t)^6 N_{n-3}(t).