1,3

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.

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, Generalizing Narayana and Schroeder Numbers to Higher Dimensions, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp.

R. A. Sulanke, Counting lattice paths by Narayana polynomials, Electron. J. Comb., vol. 7 (2000) art. 40

R. A. Sulanke, Three-dimensional Narayana and Schr\"oder numbers

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)

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

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 );

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

Adjacent sequences: A087644 A087645 A087646 this_sequence A087648 A087649 A087650

Sequence in context: A106268 A060543 A060540 this_sequence A100265 A111473 A086766

easy,nonn,tabf

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