A087647 - OEIS

%I #15 Aug 29 2016 02:49:40

%S 1,1,3,1,1,10,20,10,1,1,22,113,190,113,22,1,1,40,400,1456,2212,1456,

%T 400,40,1,1,65,1095,7095,20760,29484,20760,7095,1095,65,1,1,98,2541,

%U 26180,127435,320034,433092,320034,127435,26180,2541,98,1,1,140,5250,79870

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

%C 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.

%C 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.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

%H R. A. Sulanke, <a href="http://www.combinatorics.org/Volume_7/Abstracts/v7i1r40.html">Counting Lattice Paths by Narayana Polynomials</a> Electronic J. Combinatorics 7, No. 1, R40, 1-9, 2000.

%H R. A. Sulanke, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r54">Generalizing Narayana and Schroeder Numbers to Higher Dimensions</a>, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp.

%H R. A. Sulanke, <a href="http://dx.doi.org/10.1016/j.tcs.2005.08.014">Three-dimensional Narayana and Schröder numbers</a>, Theoretical Computer Science, Volume 346, Issues 2-3, 28 November 2005, Pages 455-468.

%F 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.

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

%e 1;

%e 1,3,1;

%e 1,10,20,10,1;

%e 1,22,113,190,113,22,1;

%e 1,40,400,1456,2212,1456,400,40,1;

%e 1,65,1095,7095,20760,29484,20760,7095,1095,65,1;

%e 1,98,2541,26180,127435,320034,433092,320034,127435,26180,2541,98,1

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

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

%K easy,nonn,tabf

%O 1,3

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