A088594 Number of 3-dimensional lattice paths running from (0,0,0) to (n,n,n), lying in {(x,y,z) : 0<=x<=y<=z} and using the steps (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1).

1, 4, 44, 788, 18372, 505156, 15553372, 520065572, 18518471492, 692900847812, 26985709712524, 1086313382608436, 44960426477218436, 1905328431907938180, 82405332511166288572, 3627806131038258219076, 162218975410046793174404

Offset: 0

Author

Robert A. Sulanke (sulanke(AT)math.boisestate.edu), Nov 20 2003

Keywords

• nonn

Comments

These are the 3-dimensional analogs of the large Schröder numbers, A006318.

R(3,n) = 4*A105124(n) for n>0, where A105124 is the three-dimensional small Schröder numbers. - Paul D. Hanna, Apr 19 2005

Number of n X 3 semi-standard Young tableaux with consecutive entries. I.e., if j is in P, and 1<=i<=j, then i is in P. - Graham H. Hawkes, Feb 16 2015

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200
• R. A. Sulanke, Three-dimensional Narayana and Schröder numbers
• R. A. Sulanke, Generalizing Narayana and Schroeder Numbers to Higher Dimensions, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp. (see page 16).

Crossrefs

Cf. A006318, A001003, A087647.

Programs

Maple

1, seq( add( 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) *2^(k+2), k = 0 .. 2*n-2), n = 1 ..20 );

Mathematica

Flatten[{1,Table[Sum[Sum[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}]*2^(k+2),{k,0,2*n-2}],{n,1,20}]}] (* Vaclav Kotesovec, Aug 14 2013 *)

PARI

{alias(C,binomial); R3(n)=if(n==0,1,sum(k=0,2*n-2, 2^(k+2)*sum(j=0,k, 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))))} \\ Paul D. Hanna, Apr 19 2005

Formula

For n => 1, R(3, n) := Sum[2^(k+2)*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}], {k, 0, 2*n-2}]. For n => 4, (3n-4)(n+2)(n+1)^2 R(3, n)(t) = (3n-2)(n+1)( 4(1+t+t^2) - 5(1+7t+t^2)n+3(1+7t+t^2)n^2 )R(3, n-1) - (n-2)( -12 +29n -30n^2 +9n^3)(1-t)^4 R(3, n-2) + (3n-1)(n-2)(n-3)(n-4) (1-t)^6 R(3, n-3).

G.f.: (1+2/x)*(1-1/x)*Int(((x-1)*(7*x^3-12*x^2+57*x+2)*hypergeom([1/3, 2/3],[1],54*x/(1-x)^3)-x*(x+5)*(x^2-8*x-11)*hypergeom([2/3, 4/3],[2],54*x/(1-x)^3))/(3*(x-1)^4*(x+2)^2),x)-(1+4*x)/(3*x). - Mark van Hoeij, Apr 16 2013

Recurrence: (n+1)^2*(n+2)*(3*n-4)*a(n) = (n+1)*(3*n-2)*(57*n^2 - 95*n + 28)*a(n-1) - (n-2)*(9*n^3 - 30*n^2 + 29*n - 12)*a(n-2) + (n-4)*(n-3)*(n-2)*(3*n-1)*a(n-3). - Vaclav Kotesovec, Aug 14 2013

a(n) ~ c*d^n/n^4, where d = 12*2^(2/3)+15*2^(1/3)+19 = 56.947628372... is the root of the equation d^3-57*d^2+3*d-1=0 and c = sqrt(4 + 10*2^(1/3)/3 + 8*2^(2/3)/3)/Pi = 1.122366540310337391196984583368763794289876... - Vaclav Kotesovec, Aug 14 2013, updated Mar 19 2015

In general, the number of SSYT of shape n X d with consecutive entries is given by:

[Prod_(i=1,d-1) (i/(n+i))^(d-1)] *

Sum_(j=0,n*(d-1)) [Prod_(i=0,d-1) (n+i+j choose n)*(Sum_(k=0,(n*(d-1)-j)) (-1)^k (n+j+k choose k)]. - Graham H. Hawkes, Feb 16 2015