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

1, 2, 6, 14, 34, 84, 208, 518, 1296, 3254, 8196, 20700, 52404, 132942, 337878, 860142, 2192902, 5598144, 14308378, 36610970, 93770358, 240390602, 616787116, 1583765724, 4069672444, 10464501074, 26924530158, 69315481778, 178545361842, 460138256784

Offset: 0

Author

Shanzhen Gao, May 13 2010

Keywords

• nonn
• walk

Comments

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

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

Examples

			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
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..750
• Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone, Card-Based ZKP Protocols for Takuzu and Juosan, 10th International Conference on Fun with Algorithms (FUN 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 20:1-21.

Crossrefs

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

Programs

Maple

b:= proc(i, j, k) option remember; `if`(i<0 or j<0, 0,
      `if`(i=0 and 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)))
    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<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 *)

Formula

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).

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)).

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)).

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

a(n) ~ (3+sqrt(5))^n * sqrt((15+7*sqrt(5))/(5*Pi*n))/2^(n-1/2). - Vaclav Kotesovec, Aug 18 2013

Extensions

Edited by Alois P. Heinz, Jun 03 2011