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
Alois P. Heinz, Table of n, a(n) for n = 0..1000
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
From Joerg Arndt, Dec 02 2013: (Start)
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:
seq(A177792(n), n=0..16) ;
# R. J. Mathar, May 31 2010
# 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):
seq(a(n), n=0..30); # Alois P. Heinz, Jun 01 2011
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];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 29 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Shanzhen Gao, May 13 2010
EXTENSIONS
More terms from R. J. Mathar, May 31 2010
Edited by Alois P. Heinz, Jun 04 2011
STATUS
approved