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 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
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.
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
KEYWORD
nonn,tabl
AUTHOR
Ioanna Arsenopoulou (io85arseno(AT)yahoo.gr), Sep 09 2010
STATUS
approved