|
|
A126086
|
|
Number of paths from (0,0,0) to (n,n,n) such that at each step (i) at least one coordinate increases, (ii) no coordinate decreases, (iii) no coordinate increases by more than 1 and (iv) all coordinates are integers.
|
|
11
|
|
|
1, 13, 409, 16081, 699121, 32193253, 1538743249, 75494983297, 3776339263873, 191731486403293, 9850349744182729, 510958871182549297, 26716694098174738321, 1406361374518034383189, 74456543501901550262689, 3961518532003397434536961, 211689479080817606497324033
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).
This is a 3-dimensional generalization of A001850.
|
|
LINKS
|
|
|
FORMULA
|
a(n) can be computed as the coefficient of (xyz)^n in the expansion of 1 / (1-x-y-z-xy-xz-yz-xyz). Also, - 2*(n+1)^2 * a(n) + (n+1)*(5n+8) * a(n+1) - 3*(37*n^2 + 146*n + 139) * a(n+2) - (55*n^2 + 389*n + 685) * a(n+3) + (n+4)^2 * a(n+4) = 0. - Max Alekseyev, Mar 03 2007
I found a very simple (although infinite) sum for the number of paths from (0,0,...,0) to (a(1),a(2),...,a(k)) using "nonzero" (2^k-1) steps of the form (x(1),x(2),...,x(k)) where x(i) is in {0,1} for 1<=i<=k, k-dimensions.
f(a(1),a(2),...,a(k)) = Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, max(a(1),a(2),...,a(k)), infinity}), Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, 0, infinity}), C(n;a)=n!/a!(n-a)! & we assumed C(n;a)=0 if n<a.
Also f(a(1),a(2),...,a(k)) can be computed as the coefficient of x(1)^a(1)...x(k)^a(k) in the expansion: 1/2 * 1/(1 - (1+x(1))*...*(1+x(k))/2). (End)
From David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007: (Start)
Using pseudo-Mathematica-style notation, f(a(1),a(2),...,a(k)) is 2^(-1 - a(1)) (a(1)!)^(k-1)/(a(2)! a(3)! ... a(k)!) * HypergeometricPFQRegularized[{1, 1 + a(1), 1 + a(1),..., 1 + a(1)}, {1, 1 + a(1) - a(2), 1 + a(1) - a(3),..., 1 + a(1) - a(k)}, 1/2]
Although it should be obvious from the above that there are k denominatorial parameters, it is not obvious that there are to be (k+1) numeratorial parameters [one of which is 1 and the other k of them are 1 + a(1)]. In other words, we have P = k + 1 and Q = k.
For information about HypergeometricPFQRegularized, see http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/ . (End)
G.f.: hypergeom([1/3,2/3],[1], 54*x/(1-x)^3)/(1-x). - Mark van Hoeij, Mar 25 2012.
Recurrence (of order 3): n^2*(3*n-4)*a(n) = (3*n-2)*(57*n^2 - 95*n + 25)*a(n-1) - (9*n^3 - 30*n^2 + 29*n - 6)*a(n-2) + (n-2)^2*(3*n-1)*a(n-3). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ c * d^n / n, where d = 12*2^(2/3)+15*2^(1/3)+19 = 56.947628372041491... and c = 0.2805916350775843477992461458421909485724690193829181355064... = sqrt((6 + 5*2^(1/3) + 4*2^(2/3))/6)/(2*Pi). - Vaclav Kotesovec, Mar 15 2014, updated Mar 22 2016
a(n) = Sum_{0 <= j, k <= n} C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). Cf. A001850 and A274668.
a(n) = Sum_{0 <= j, k <= n} (-2)^(j+k)*C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). (End)
|
|
EXAMPLE
|
Illustrating a(1) = 13:
000 -> 001 -> 011 -> 111
000 -> 001 -> 101 -> 111
000 -> 001 -> 111
000 -> 010 -> 011 -> 111
000 -> 010 -> 110 -> 111
000 -> 010 -> 111
000 -> 100 -> 101 -> 111
000 -> 100 -> 110 -> 111
000 -> 100 -> 111
000 -> 011 -> 111
000 -> 101 -> 111
000 -> 110 -> 111
000 -> 111
|
|
MAPLE
|
f := proc(n) local i, k; add(add((-1)^k*binomial(k, i)*(-1)^i*binomial(i, n)^3, i=n..k), k=n..3*n) end: # Brendan McKay, Mar 03 2007
seq(sum(binomial(k, n)^3/2^(k+1), k=n..infinity), n=0..10); # Vladeta Jovovic, Mar 01 2008
|
|
MATHEMATICA
|
m = 14; se = Series[1/(1 - x - y - z - x*y - x*z - y*z - x*y*z), {x, 0, m}, {y, 0, m}, {z, 0, m}]; a[n_] := Coefficient[se, (x*y*z)^n]; a[0] = 1; Table[a[n], {n, 0, m}] (* Jean-François Alcover, Sep 27 2011, after Max Alekseyev *)
Table[Sum[Sum[(-1)^k*Binomial[k, i]*(-1)^i*Binomial[i, n]^3, {i, n, k}], {k, n, 3*n}], {n, 0, 20}] (* Vaclav Kotesovec, Mar 15 2014, after Brendan McKay *)
|
|
PROG
|
(Python) # Naive version - see link for better version.
def f(a, b):
if a == 0 or b == 0:
return 1
return f(a, b - 1) + f(a - 1, b) + f(a - 1, b - 1)
def g(a, b, c):
if a == 0:
return f(b, c)
if b == 0:
return f(c, a)
if c == 0:
return f(a, b)
return (
g(a, b, c - 1)
+ g(a, b - 1, c)
+ g(a - 1, b, c)
+ g(a, b - 1, c - 1)
+ g(a - 1, b, c - 1)
+ g(a - 1, b - 1, c)
+ g(a - 1, b - 1, c - 1)
)
for n in range(6):
print(g(n, n, n), end=", ")
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|