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

Author

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

Keywords

• nonn
• tabl

Comments

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

Examples

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

Links

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

Crossrefs

See A239101 for another version of this triangle or array.

Cf. A124445.

Programs

Magma

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

Mathematica

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

Formula

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