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.

%I A180562 #71 Apr 01 2024 02:41:51
%S A180562 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 A180562 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 A180562 45,70,83,70,37,10,1,1,2,11,25,56,96,131,136,100,46,11
%N A180562 Triangle read by rows: T(n,k) = number of binary words of length n avoiding 010 and having k 1's.
%C A180562 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 A180562 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 A180562 Row sums yield sequence A005251. Alternating row sums yield sequence A000931. - _John M. Campbell_, Apr 20 2012
%C A180562 Can also be regarded as an infinite array read by antidiagonals [Baccherini et al., 2007]. - _N. J. A. Sloane_, Mar 25 2014
%H A180562 Alois P. Heinz, <a href="/A180562/b180562.txt">Rows n = 0..140, flattened</a>
%H A180562 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 A180562 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 A180562 G.f.: (1+x^2*y)/(1-x-x*y+x^2*y-x^3*y^2).
%F A180562 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 A180562 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 A180562 Triangle begins:
%e A180562   1;
%e A180562   1, 1;
%e A180562   1, 2, 1;
%e A180562   1, 2, 3,  1;
%e A180562   1, 2, 4,  4,  1;
%e A180562   1, 2, 5,  7,  5,  1;
%e A180562   1, 2, 6, 10, 11,  6,  1;
%e A180562   1, 2, 7, 13, 18, 16,  7, 1;
%e A180562   1, 2, 8, 16, 26, 30, 22, 8, 1;
%e A180562 T(5,3)=7 because we have 00111, 01101, 01110, 10011, 10110, 11001, 11100.
%e A180562 As an infinite square array:
%e A180562   1 1 1  1  1  1   1 ...
%e A180562   1 2 3  4  5  6   7 ...
%e A180562   1 2 4  7 11 16  22 ...
%e A180562   1 2 5 10 18 30  47 ...
%e A180562   1 2 6 13 26 48  83 ...
%e A180562   1 2 7 16 35 70 131 ...
%e A180562   1 2 8 19 45 96 192 ...
%e A180562   ...
%t A180562 Series[(1 + x^2*y)/(1- x - x*y + x^2*y - x^3*y^2), {x, 0, 20}, {y, 0, 10}]
%t A180562 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 A180562 (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 A180562 See A239101 for another version of this triangle or array.
%Y A180562 Cf. A124445.
%K A180562 nonn,tabl
%O A180562 0,5
%A A180562 Ioanna Arsenopoulou (io85arseno(AT)yahoo.gr), Sep 09 2010