login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177790 Number of paths from (0,0) to (n,n) avoiding 3 or more consecutive east steps and 3 or more consecutive north steps. 3
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 (list; graph; refs; listen; history; text; internal format)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 07:58 EDT 2019. Contains 327168 sequences. (Running on oeis4.)