login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180562 Triangle read by rows: T(n,k)=number of binary words of length n avoiding 010 and having k 1's. 3
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,5
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 sub-sub-diagonal, 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
LINKS
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.
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
EXAMPLE
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 ...
...
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 *)
PROG
(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
CROSSREFS
See A239101 for another version of this triangle or array.
Cf. A124445.
Sequence in context: A027751 A181322 A004070 * A199711 A048887 A360493
KEYWORD
nonn,tabl
AUTHOR
Ioanna Arsenopoulou (io85arseno(AT)yahoo.gr), Sep 09 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:16 EDT 2024. Contains 371264 sequences. (Running on oeis4.)