login
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).
2
1, 4, 44, 788, 18372, 505156, 15553372, 520065572, 18518471492, 692900847812, 26985709712524, 1086313382608436, 44960426477218436, 1905328431907938180, 82405332511166288572, 3627806131038258219076, 162218975410046793174404
OFFSET
0,2
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
R. A. Sulanke, Generalizing Narayana and Schroeder Numbers to Higher Dimensions, Electron. J. Combin. 11 (2004), Research Paper 54, 20 pp. (see page 16).
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert A. Sulanke (sulanke(AT)math.boisestate.edu), Nov 20 2003
STATUS
approved