A239101 -id:A239101 - cp's OEIS frontend

A180562 Triangle read by rows: T(n,k) = number of binary words of length n avoiding 010 and having k 1's.

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 4, 1, 1, 2, 5, 7, 5, 1, 1, 2, 6, 10, 11, 6, 1, 1, 2, 7, 13, 18, 16, 7, 1, 1, 2, 8, 16, 26, 30, 22, 8, 1, 1, 2, 9, 19, 35, 48, 47, 29, 9, 1, 1, 2, 10, 22, 45, 70, 83, 70, 37, 10, 1, 1, 2, 11, 25, 56, 96, 131, 136, 100, 46, 11

Offset: 0

Ioanna Arsenopoulou (io85arseno(AT)yahoo.gr), Sep 09 2010

T(n+k-1,k-1) also gives the number of nonnegative integer solutions of x_1 + x_2 + ... + x_k = n, such that every two consecutive terms cannot be both nonzero.
Absolute values of coefficients of the characteristic polynomial of square matrices with 1's along and everywhere above the main diagonal, 1's along the subsubdiagonal, and 0's everywhere else. - John M. Campbell, Aug 20 2011
Row sums yield sequence A005251. Alternating row sums yield sequence A000931. - John M. Campbell, Apr 20 2012
Can also be regarded as an infinite array read by antidiagonals [Baccherini et al., 2007]. - N. J. A. Sloane, Mar 25 2014

			Triangle begins:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 3,  1;
  1, 2, 4,  4,  1;
  1, 2, 5,  7,  5,  1;
  1, 2, 6, 10, 11,  6,  1;
  1, 2, 7, 13, 18, 16,  7, 1;
  1, 2, 8, 16, 26, 30, 22, 8, 1;
T(5,3)=7 because we have 00111, 01101, 01110, 10011, 10110, 11001, 11100.
As an infinite square array:
  1 1 1  1  1  1   1 ...
  1 2 3  4  5  6   7 ...
  1 2 4  7 11 16  22 ...
  1 2 5 10 18 30  47 ...
  1 2 6 13 26 48  83 ...
  1 2 7 16 35 70 131 ...
  1 2 8 19 45 96 192 ...
  ...

Alois P. Heinz, Rows n = 0..140, flattened
D. Baccherini, D. Merlini, and R. Sprugnoli, Binary words excluding a pattern and proper Riordan arrays, Discrete Math. 307 (2007), no. 9-10, 1021--1037. MR2292531 (2008a:05003). See top of p. 1022. - _N. J. A. Sloane_, Mar 25 2014
David Eppstein, Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time, arXiv:2303.00147 [cs.CG], 2023, p. 9.

See A239101 for another version of this triangle or array.

Cf. A124445.

/* As triangle: */ [[&+[(-1)^j*Binomial(n-k-1,j)*Binomial(n-2*j,k-j): j in [0..n-k]]: k in [0..n]]: n in [0..11]]; // Bruno Berselli, Jan 30 2013

Series[(1 + x^2*y)/(1- x - x*y + x^2*y - x^3*y^2), {x, 0, 20}, {y, 0, 10}]
t[n_, k_] := Sum[(-1)^j*Binomial[n - k - 1, j]*Binomial[n - 2*j, k - j], {j, 0, n - k}]; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 30 2013 *)

G.f.: (1+x^2*y)/(1-x-x*y+x^2*y-x^3*y^2).
T(n,k) = Sum_{j=0..n-k} (-1)^j * C(n-k-1,j) * C(abs(n-2*j),k-j) with k=0..n.
T(n,k) = T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) + T(n-3,k-2), T(0,0) = T(1,0) = T(1,1) = T(2,0) = T(2,2) = 1, T(2,1) = 2, T(nk) = 0 if k < 0 or if k > n. - Philippe Deléham, Mar 25 2014

A225034 a(n) is the number of binary words containing n 1's and at most n 0's that do not contain the substring 101.

Original entry on oeis.org

1, 3, 7, 18, 48, 131, 363, 1017, 2873, 8169, 23349, 67024, 193086, 557949, 1616501, 4694034, 13657896, 39809649, 116218701, 339762942, 994553160, 2914608177, 8550424953, 25107964077, 73793368593, 217057617567, 638936722403, 1882096946232, 5547613247418, 16361808691243

Offset: 0

Elisabetta Grazzini, May 02 2013

Number of weakly increasing words of length n+1 with n+2 letters such that no up-step is by 1, see example. - Joerg Arndt, Jun 10 2013

Row sums of the Riordan array in A239101. - Philippe Deléham, Mar 25 2014

			The binary words having two 1's (n=2) and at most two 0's and which do not have 101 as a substring are:
01: 11,
02: 1001,
03: 011,
04: 0110,
05: 110,
06: 1100,
07: 0011,
therefore a(2)=7.
The binary words having three 1's (n=3) and at most three 0's and which do not have 101 as a substring are:
01: 111,
02: 1110,
03: 0111,
04: 11100,
05: 11001,
06: 10011,
07: 00111,
08: 01110,
09: 111000,
10: 110001,
11: 100011,
12: 000111,
13: 011100,
14: 001110,
15: 010011,
16: 011001,
17: 100110,
18: 110010,
therefore a(3)=18.
From _Joerg Arndt_, Jun 10 2013: (Start)
There are a(3)=18 weakly increasing length-4 words of 5 letters (0,1,2,3,4) with no up-step by 1:
01:  [ 0 0 0 ]
02:  [ 0 0 2 ]
03:  [ 0 0 3 ]
04:  [ 0 0 4 ]
05:  [ 0 2 2 ]
06:  [ 0 2 4 ]
07:  [ 0 3 3 ]
08:  [ 0 4 4 ]
09:  [ 1 1 1 ]
10:  [ 1 1 3 ]
11:  [ 1 1 4 ]
12:  [ 1 3 3 ]
13:  [ 1 4 4 ]
14:  [ 2 2 2 ]
15:  [ 2 2 4 ]
16:  [ 2 4 4 ]
17:  [ 3 3 3 ]
18:  [ 4 4 4 ]
(End)

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
Stefano Bilotta, Elisabetta Grazzini, and Elisa Pergola, Counting Binary Words Avoiding Alternating Patterns, J. Integer Seq., 16 (2013), Article 13.4.8.
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

Cf. A005251, A239101.

CoefficientList[Series[2 (1 - x^2)/(3 x^2 - 4 x + 1 + Sqrt[(1 - x^2)^2 - 4 (x - x^2) (1 - x^2)]), {x, 0, 30}], x] (* Bruno Berselli, May 02 2013 *)

x='x+O('x^66); Vec((2*(1-x^2))/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2)))) \\ Joerg Arndt, May 02 2013

Theorem: G.f. = 2*(1-x^2)/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2))).
Conjecture: (n+1)*a(n) - (2*n+3)*a(n-1) - 3*(n-2)*a(n-2) = 0 for n>1. - Bruno Berselli, May 02 2013
a(n) ~ 4*3^(n-1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
a(n) = Sum_{k = 0..n} A239101(n,k). - Philippe Deléham, Mar 25 2014

cp's OEIS Frontend

A180562 Triangle read by rows: T(n,k) = number of binary words of length n avoiding 010 and having k 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula