|
|
A177792
|
|
Number of paths from (0,0) to (n,n) avoiding 4 or more consecutive east steps and 4 or more consecutive north steps.
|
|
1
|
|
|
1, 2, 6, 20, 62, 194, 616, 1972, 6344, 20498, 66486, 216352, 705982, 2309246, 7569420, 24857864, 81768144, 269369282, 888569354, 2934666604, 9702925752, 32113058042, 106379839060, 352698604852, 1170271492014, 3885821473458, 12911299418962, 42926732404728
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of binary strings of length 2*n containing n zeros and n ones, avoiding the patterns 0000 and 1111, see example. [Joerg Arndt, Dec 02 2013]
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*Sum_{i=0..floor(n/3)} Sum_{j=0..floor((n-3*i)/2)} C(n-2*i-j,i) * C(n-3*i-j,j) * (Sum_{s=0..min(floor(n/3), floor((2*i+j)/2))} C(n-2*i-j,s) * C(n-2*i-j-s, 2*i+j-2*s) + Sum_{s=0..min(floor(n/3), floor((2*i+j+1)/2))} C(n-2*i-j-1,s) * C(n-2*i-j-s-1, 2*i+j+1-2*s)) if n>0; a(0) = 1.
a(n) = [x^n y^n] (1+x+x^2+x^3)*(1+y+y^2+y^3) / (1-x*y-x*y^2 -x*y^3-x^2*y -x^2*y^2-x^2*y^3 -x^3*y-x^3*y^2 -x^3*y^3).
a(n) ~ c * d^n / sqrt(Pi*n), where d = 1 + 1/3*(54-6*sqrt(33))^(1/3) + (2*(9+sqrt(33)))^(1/3) / 3^(2/3) = 3.382975767906237494122708536455034586... is the root of the equation 1 + d + 3*d^2 - d^3 = 0, and c = 2.106003170801818641958056379397216... is the root of the equation -4 - 80*c^2 - 616*c^4 + 143*c^6 = 0. - Vaclav Kotesovec, Aug 22 2014
|
|
EXAMPLE
|
The a(3) = 20 binary strings of length 3 containing 3 zeros and 3 ones, avoiding the patterns 0000 and 1111 are (putting dots for zeros)
01: [ . . . 1 1 1 ]
02: [ . . 1 . 1 1 ]
03: [ . . 1 1 . 1 ]
04: [ . . 1 1 1 . ]
05: [ . 1 . . 1 1 ]
06: [ . 1 . 1 . 1 ]
07: [ . 1 . 1 1 . ]
08: [ . 1 1 . . 1 ]
09: [ . 1 1 . 1 . ]
10: [ . 1 1 1 . . ]
11: [ 1 . . . 1 1 ]
12: [ 1 . . 1 . 1 ]
13: [ 1 . . 1 1 . ]
14: [ 1 . 1 . . 1 ]
15: [ 1 . 1 . 1 . ]
16: [ 1 . 1 1 . . ]
17: [ 1 1 . . . 1 ]
18: [ 1 1 . . 1 . ]
19: [ 1 1 . 1 . . ]
20: [ 1 1 1 . . . ]
(End)
|
|
MAPLE
|
A177792a := proc(n, i, j, s, l) binomial(n-2*i-j, i)*binomial(n-3*i-j, j)*binomial(n-2*i-j-l, s) *binomial(n-2*i-j-l-s, 2*i+j-2*s+l) ; end proc:
A177792 := proc(n) local a, i, j, slim, s ; if n=0 then return(1) fi; a := 0 ; for i from 0 to n/3 do for j from 0 to (n-3*i)/2 do slim := min( n/3, i+j/2) ; a := a+add( A177792a(n, i, j, s, 0), s=0..slim) ; slim := min( n/3, i+(j+1)/2) ; a := a+add( A177792a(n, i, j, s, 1), s=0..slim) ; end do: end do: 2*a; end proc:
# second Maple Program:
b:= proc(i, j, k) option remember; `if`(i<0 or j<0, 0,
`if`(i=0 and j=0, 1, `if`(k<3, b(i-1, j, max(k, 0)+1), 0)+
`if`(k>-3, b(i, j-1, min(k, 0)-1), 0)))
end:
a:= n-> b(n, n, 0):
|
|
MATHEMATICA
|
b[i_, j_, k_] := b[i, j, k] = If[i<0 || j<0, 0, If[i==0 && j==0, 1, If[k<3, b[i-1, j, Max[k, 0]+1], 0] + If[k > -3, b[i, j-1, Min[k, 0]-1], 0]]];
a[n_] := b[n, n, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|