|
|
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
Can also be regarded as an infinite array read by antidiagonals [Baccherini et al., 2007]. - N. J. A. Sloane, Mar 25 2014
|
|
LINKS
|
|
|
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.
|
|
KEYWORD
|
|
|
AUTHOR
|
Ioanna Arsenopoulou (io85arseno(AT)yahoo.gr), Sep 09 2010
|
|
STATUS
|
approved
|
|
|
|