OFFSET
1,3
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.
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.
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).
EXAMPLE
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
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 );
CROSSREFS
KEYWORD
easy,nonn,tabf
AUTHOR
Robert A. Sulanke (sulanke(AT)math.boisestate.edu), Sep 23 2003
STATUS
approved