|
| |
|
|
A087647
|
|
Triangle of 3-Narayana numbers, N(n,k), for n >= 1, 0 <= k <= 2n-2.
|
|
1
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
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.
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| 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
|
|
|
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
| 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).
Sequence in context: A176156 A172339 A060540 * A100265 A086766 A078688
Adjacent sequences: A087644 A087645 A087646 * A087648 A087649 A087650
|
|
|
KEYWORD
| easy,nonn,tabf
|
|
|
AUTHOR
| Robert A. Sulanke (sulanke(AT)math.boisestate.edu), Sep 23 2003
|
| |
|
|
