A003440 -id:A003440 - cp's OEIS frontend

A078678 Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.

1, 2, 4, 8, 18, 42, 100, 242, 592, 1460, 3624, 9042, 22656, 56970, 143688, 363348, 920886, 2338566, 5949148, 15157874, 38674978, 98803052, 252701484, 646990518, 1658066668, 4252908542, 10917422860, 28046438252, 72099983802, 185469011130, 477383400300

Offset: 0

Emanuele Munarini, Dec 17 2002

nonn

Also number of Grand Dyck paths of length 2*n with no zigzags, that is, with no factors UDU or DUD. - Emanuele Munarini, Jul 07 2011

			For n = 2 : 0011, 0110, 1001, 1100.
For n = 3 : 000111, 011001, 100011, 110001, 001110, 011100, 100110, 111000.

Vincenzo Librandi, Table of n, a(n) for n = 0..220
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
T. Doslic, Seven lattice paths to log-convexity, Acta Appl. Mathem. 110 (3) (2010) 1373-139, eq 4.
Emanuele Munarini and N. Z. Salvi, Binary strings without zigzags, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, arXiv:math/0512548 [math.CO], 2007.

Cf. A078679, A128588.
Cf. A003440.
Main diagonal of array A099172.
Related to diagonal of rational functions: A268545-A268555.

a:= proc(n) option remember; `if`(n<5, [1, 2, 4, 8, 18][n+1],
     (2*n*a(n-1)+(n-2)*a(n-2)+(2*n-8)*a(n-3)-(n-4)*a(n-4))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 13 2020

Table[SeriesCoefficient[Series[Sqrt[(1 + x + x^2)/(1 - 3 x + x^2)], {x, 0, n}], n], {n, 0, 40}]

a(n):=coeff(taylor((1+x+x^2)/sqrt(1-2*x-x^2-2*x^3+x^4),x,0,n),x,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Jul 07 2011 */

my(x='x+O('x^99)); Vec(((1+x+x^2)/(1-3*x+x^2))^(1/2)) \\ Altug Alkan, Jul 18 2016

G.f.: sqrt( ( 1 + x + x^2 ) / ( 1 - 3*x + x^2 ) ).
a(n) = Sum_{k=0..n+floor(n/2)} binomial( n - k + 2*floor(k/3), floor(k/3) )^2.
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)^2*( 2*n^2 - 6*n*k + 6*k^2 )/(n-k)^2, n > 0.
a(n) ~ 2 * ((3+sqrt(5))/2)^n / (5^(1/4)*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 21 2014
a(n) = [x^n y^n](1+x*y+x^2*y^2)/(1-x-y+x*y-x^2*y^2). - Gheorghe Coserea, Jul 18 2016
D-finite with recurrence: n*a(n) -2*n*a(n-1) +(-n+2)*a(n-2) +2*(-n+4)*a(n-3) +(n-4)*a(n-4)=0. [Doslic] - R. J. Mathar, Jun 21 2018

A268159 T(n,k)=Number of nXk arrays containing k copies of 0..n-1 with every element equal to at least one vertical or antidiagonal neighbor and the top left element equal to 0.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 3, 8, 6, 0, 0, 7, 14, 36, 0, 0, 0, 17, 52, 906, 456, 120, 0, 0, 42, 1516, 31818, 23592, 6360, 0, 0, 0, 104, 7582, 770406, 10213152, 3304920, 93600, 5040, 0, 0, 259, 46338, 28194516, 871718016, 4067565720, 334738800, 1784160, 0, 0, 0, 648

Offset: 1

R. H. Hardin, Jan 27 2016

Table starts
.0....0.......0.........0..........0.............0............0.........0
.0....1.......1.........3..........7............17...........42.......104
.0....0.......8........14.........52..........1516.........7582.....46338
.0....6......36.......906......31818........770406.....28194516.857204082
.0....0.....456.....23592...10213152.....871718016.131259920304
.0..120....6360...3304920.4067565720.2310125813160
.0....0...93600.334738800
.0.5040.1784160
.0....0
.0

			Some solutions for n=4 k=4
..0..3..3..1....0..3..2..3....0..3..1..2....0..2..1..2....0..0..1..1
..0..3..2..1....0..3..2..3....0..3..1..2....0..2..1..2....0..1..2..1
..3..2..0..1....1..1..0..2....3..0..2..1....1..3..0..3....0..2..3..3
..2..2..0..1....1..1..0..2....3..0..2..1....1..3..0..3....2..2..3..3

R. H. Hardin, Table of n, a(n) for n = 1..61

Column 2 is A005212(n-1).

Row 2 is A003440(n-2).

A104402 Matrix inverse of triangle A091491, read by rows.

Original entry on oeis.org

1, -1, 1, 1, -2, 1, 0, 2, -3, 1, 0, -1, 4, -4, 1, 0, 0, -3, 7, -5, 1, 0, 0, 1, -7, 11, -6, 1, 0, 0, 0, 4, -14, 16, -7, 1, 0, 0, 0, -1, 11, -25, 22, -8, 1, 0, 0, 0, 0, -5, 25, -41, 29, -9, 1, 0, 0, 0, 0, 1, -16, 50, -63, 37, -10, 1, 0, 0, 0, 0, 0, 6, -41, 91, -92, 46, -11, 1, 0, 0, 0, 0, 0, -1, 22, -91, 154, -129, 56, -12, 1

Offset: 0

Paul D. Hanna, Mar 05 2005

Row sums are all 0's for n>0. Absolute row sums form 2*A000045(n+1) for n>0, where A000045 = Fibonacci numbers. Sums of squared terms in row n = 2*A003440(n) for n>0, where A003440 = number of binary vectors with restricted repetitions.

Riordan array (1-x+x^2, x(1-x)). - Philippe Deléham, Nov 04 2009

			Triangle begins as:
   1;
  -1,  1;
   1, -2,  1;
   0,  2, -3,  1;
   0, -1,  4, -4,   1;
   0,  0, -3,  7,  -5,   1;
   0,  0,  1, -7,  11,  -6,  1;
   0,  0,  0,  4, -14,  16, -7,  1;
   0,  0,  0, -1,  11, -25, 22, -8, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A000045, A003440, A091491, A199881.

Table[(-1)^(n-k)*(Binomial[k, n-k] + Binomial[k+1, n-k-1]), {n,0,12}, {k,0,n}] //Flatten (* G. C. Greubel, Apr 30 2021 *)

T(n,k)=local(X=x+x*O(x^n),Y=y+y*O(y^k)); polcoeff(polcoeff((1-X+X^2)/(1-X*Y*(1-X)),n,x),k,y)

PARI
```
T(n,k)=if(n
				
```

T(n,k)=(-1)^(n-k)*(binomial(k,n-k)+binomial(k+1,n-k-1))

def A104402(n,k): return (-1)^(n+k)*(binomial(k,n-k) + binomial(k+1,n-k-1))
flatten([[A104402(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Apr 30 2021

G.f.: (1-x+x^2)/(1-x*y*(1-x)).
T(n, k) = T(n-1, k-1) - T(n-2, k-1) for k>0 with T(0, 0)=1, T(1, 0)=-1, T(2, 0)=1, T(n, 0)=0 (n>2).
T(n, k) = (-1)^(n-k)*(C(k, n-k) + C(k+1, n-k-1)).
From Philippe Deléham, Nov 04 2009: (Start)
Sum_{k=0..n} T(n,k) = 0^n.
Sum_{k=0..n} abs(T(n, k)) = 2*Fibonacci(n+1) - [n=0].
Sum_{k=0..n} ( T(n,k) )^2 = 2*A003440(n) - [n=0]. (End)

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

Original entry on oeis.org

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

Shanzhen Gao, May 13 2010

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

			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

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.

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

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

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

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

Edited by Alois P. Heinz, Jun 03 2011

A253316 Number of 2n X 2n Takuzu grids.

Original entry on oeis.org

1, 2, 72, 4140, 4111116, 48183195384

Offset: 0

Brian Kell, Dec 30 2014

A Takuzu grid is a 2n X 2n zero-one matrix with the following properties:
Every row and every column has n zeros and n ones.
No row or column has three consecutive zeros or three consecutive ones.
All rows are distinct, and all columns are distinct (but a row may be the same as a column).

			The following is a 4 X 4 Takuzu grid:
[ 0  1  1  0 ]
[ 1  0  0  1 ]
[ 0  0  1  1 ]
[ 1  1  0  0 ]

Wikipedia, Takuzu

Cf. A058527.

Number of possible rows equals A003440.

a(5) from Frans J. Faase, Dec 14 2015

cp's OEIS Frontend

A078678 Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A268159 T(n,k)=Number of nXk arrays containing k copies of 0..n-1 with every element equal to at least one vertical or antidiagonal neighbor and the top left element equal to 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A104402 Matrix inverse of triangle A091491, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A253316 Number of 2n X 2n Takuzu grids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions