login
Number of paths from (0,0) to (n,n) avoiding 3 or more consecutive east steps and 3 or more consecutive north steps.
3

%I #28 Nov 25 2020 21:19:10

%S 1,2,6,14,34,84,208,518,1296,3254,8196,20700,52404,132942,337878,

%T 860142,2192902,5598144,14308378,36610970,93770358,240390602,

%U 616787116,1583765724,4069672444,10464501074,26924530158,69315481778,178545361842,460138256784

%N Number of paths from (0,0) to (n,n) avoiding 3 or more consecutive east steps and 3 or more consecutive north steps.

%C a(n) equals the number of different permutations of n 0's and n 1's such that no more than two occurrences of the same number ever appear in a row. - _Dave R.M. Langers_, Apr 07 2016

%C This also equals the number of possible different rows or columns that may occur in a 2n-by-2n binary puzzle. - _Dave R.M. Langers_, Apr 07 2016

%H Alois P. Heinz, <a href="/A177790/b177790.txt">Table of n, a(n) for n = 0..750</a>

%H Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, Hideaki Sone, <a href="https://drops.dagstuhl.de/opus/volltexte/2020/12760/pdf/lipics-vol157-fun2021-complete.pdf#page=339">Card-Based ZKP Protocols for Takuzu and Juosan</a>, 10th International Conference on Fun with Algorithms (FUN 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 20:1-21.

%F a(n) = Sum_{i=0..floor(n/2)} 2*C(n-i,i)^2 + C(n-i,i)*C(n-i-1,i+1) + C(n-i,i)*C(n-i+1,i-1).

%F a(n) = [x^n y^n] (-(1+x+x^2)*(1+y+y^2) / (-1+x*y+x*y^2+x^2*y+x^2*y^2)).

%F G.f.: 1 + ((1-t)^2*sqrt((1+t+t^2)*(1-3*t+t^2))-(1-3*t+t^2)*(1+t^2)) / (t^2*(1-3*t+t^2)).

%F Recurrence: (n-2)*(n-1)*(n+2)*a(n) = 2*(n-2)*n*(n+1)*a(n-1) + (n-1)*(n^2 - 2*n - 4)*a(n-2) + 2*(n-3)*(n-2)*n*a(n-3) - (n-4)*(n-1)*n*a(n-4). - _Vaclav Kotesovec_, Aug 18 2013

%F a(n) ~ (3+sqrt(5))^n * sqrt((15+7*sqrt(5))/(5*Pi*n))/2^(n-1/2). - _Vaclav Kotesovec_, Aug 18 2013

%e For n=3, the a(3)=14 possible arrangements are 001011, 001101, 010011, 010101, 010110, 011001, 011010, 100101, 100110, 101001, 101010, 101100, 110010, and 110100. - _Dave R.M. Langers_, Apr 07 2016

%p b:= proc(i, j, k) option remember; `if`(i<0 or j<0, 0,

%p `if`(i=0 and j=0, 1, `if`(k<2, b(i-1, j, max(k, 0)+1), 0)+

%p `if`(k>-2, b(i, j-1, min(k, 0)-1), 0)))

%p end:

%p a:= n-> b(n, n, 0):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jun 01 2011

%t b[i_, j_, k_] := b[i, j, k] = If[i<0 || j<0, 0, If[i == 0 && j == 0, 1, If[k<2, b[i-1, j, Max[k, 0]+1], 0] + If[k > -2, 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_, Jan 19 2015, after _Alois P. Heinz_ *)

%Y Equals twice A003440 (number of binary vectors with restricted repetitions).

%K nonn,walk

%O 0,2

%A _Shanzhen Gao_, May 13 2010

%E Edited by _Alois P. Heinz_, Jun 03 2011