A180562 - OEIS

%I #71 Apr 01 2024 02:41:51

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

%T 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,

%U 45,70,83,70,37,10,1,1,2,11,25,56,96,131,136,100,46,11

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

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

%C 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

%C Row sums yield sequence A005251. Alternating row sums yield sequence A000931. - _John M. Campbell_, Apr 20 2012

%C Can also be regarded as an infinite array read by antidiagonals [Baccherini et al., 2007]. - _N. J. A. Sloane_, Mar 25 2014

%H Alois P. Heinz, <a href="/A180562/b180562.txt">Rows n = 0..140, flattened</a>

%H D. Baccherini, D. Merlini, and R. Sprugnoli, <a href="http://dx.doi.org/10.1016/j.disc.2006.07.023">Binary words excluding a pattern and proper Riordan arrays</a>, Discrete Math. 307 (2007), no. 9-10, 1021--1037. MR2292531 (2008a:05003). See top of p. 1022. - _N. J. A. Sloane_, Mar 25 2014

%H David Eppstein, <a href="https://arxiv.org/abs/2303.00147">Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time</a>, arXiv:2303.00147 [cs.CG], 2023, p. 9.

%F G.f.: (1+x^2*y)/(1-x-x*y+x^2*y-x^3*y^2).

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

%F 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

%e Triangle begins:

%e   1;

%e   1, 1;

%e   1, 2, 1;

%e   1, 2, 3,  1;

%e   1, 2, 4,  4,  1;

%e   1, 2, 5,  7,  5,  1;

%e   1, 2, 6, 10, 11,  6,  1;

%e   1, 2, 7, 13, 18, 16,  7, 1;

%e   1, 2, 8, 16, 26, 30, 22, 8, 1;

%e T(5,3)=7 because we have 00111, 01101, 01110, 10011, 10110, 11001, 11100.

%e As an infinite square array:

%e   1 1 1  1  1  1   1 ...

%e   1 2 3  4  5  6   7 ...

%e   1 2 4  7 11 16  22 ...

%e   1 2 5 10 18 30  47 ...

%e   1 2 6 13 26 48  83 ...

%e   1 2 7 16 35 70 131 ...

%e   1 2 8 19 45 96 192 ...

%e   ...

%t Series[(1 + x^2*y)/(1- x - x*y + x^2*y - x^3*y^2), {x, 0, 20}, {y, 0, 10}]

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

%o (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

%Y See A239101 for another version of this triangle or array.

%Y Cf. A124445.

%K nonn,tabl

%O 0,5

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