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,2

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

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

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

Example

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

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

Crossrefs

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

Sequence in context: A182644 A099425 A186523 * A307068 A269506 A292816

Adjacent sequences: A177787 A177788 A177789 * A177791 A177792 A177793

Keyword

nonn,walk

Author

Shanzhen Gao, May 13 2010

Extensions

Edited by Alois P. Heinz, Jun 03 2011

Status

approved