A158909 Riordan array (1/((1-x)(1-x^2)), x/(1-x)^2). Triangle read by rows, T(n,k) for 0 <= k <= n.

1, 1, 1, 2, 3, 1, 2, 7, 5, 1, 3, 13, 16, 7, 1, 3, 22, 40, 29, 9, 1, 4, 34, 86, 91, 46, 11, 1, 4, 50, 166, 239, 174, 67, 13, 1, 5, 70, 296, 553, 541, 297, 92, 15, 1, 5, 95, 496, 1163, 1461, 1068, 468, 121, 17, 1, 6, 125, 791, 2269, 3544, 3300, 1912, 695, 154, 19, 1

Offset: 0

Author

Paul Barry, Mar 30 2009

Keywords

• easy
• nonn
• tabl

Comments

Diagonal sums are the Jacobsthal numbers A001045.

Transforms r^n into the symmetric third-order sequence with g.f. 1/(1-(r+1)x-(r+1)x^2+x^3), see the formulas.

From Wolfdieter Lang, Oct 22 2019: (Start)

The signed triangle t(n, k) = (-1)^(n-k)*T(n, k) appears in the expansion [n+2, 2]q / q^n = Sum{k=0} t(n, k)*y^(2*k), with y = q^(1/2) + q^(-1/2), where [n+2, 2]_q are q-binomial coefficients (see A008967, but with a different offset). The formula is [n+2, 2]_q / q^n = S(n+1, y)*S(n, y)/y with Chebyshev S polynomials (A049310). This is a polynomial in y^2 but not in q after replacement of the given y = y(q).

The A-sequence for this Riordan triangle is A(n) = (-1)^n*A115141(n) with o.g.f A(x) = 1 + x*(1 + c(-x)), with c(x) generating A000108 (Catalan).

The Z-sequence is z(n) = (-1)^(n+1)*A071724(n), for n >= 1 and z(0) = 1. The o.g.f. is Z(x) = 1 + x*c(-x)^3. See A071724 for a link on A- and Z-sequences, and their use for the recurrence. (End)

T(n,k) is the number of tilings of a (2*n+1)-board (a 1 X (2*n+1) rectangular board) using 2*k+1 squares and 2*(n-k) (1,1)-fences. A (1,1)-fence is a tile composed of two squares separated by a gap of width 1. - Michael A. Allen, Mar 20 2021

Examples

			From _Wolfdieter Lang_, Oct 22 2019: (Start)
The triangle T(n, k) begins:
  n\k  0   1   2    3    4    5    6   7   8  9 10 ...
  ----------------------------------------------------
  0:   1
  1:   1   1
  2:   2   3   1
  3:   2   7   5    1
  4:   3  13  16    7    1
  5:   3  22  40   29    9    1
  6:   4  34  86   91   46   11    1
  7:   4  50 166  239  174   67   13   1
  8:   5  70 296  553  541  297   92  15   1
  9:   5  95 496 1163 1461 1068  468 121  17  1
  10:  6 125 791 2269 3544 3300 1912 695 154 19  1
  ...
----------------------------------------------------------------------------
Recurrence: T(5, 2) = 16 + 13 + 5 + 7 - 1 = 40, and T(5, 0) = 3 + 2 - 2 = 3. [using _Philippe Deléham_'s Nov 12 2013 recurrence]
Recurrence from A-sequence [1, 2, -1, 2, -5, ...]: T(5, 2) = 1*13 + 2*16 - 1*7 + 2*1 = 40.
Recurrence from Z-sequence [1, 1, -3, 9, -28, ...]: T(5, 0) = 1*3 + 1*13 - 3*16 + 9*7 - 28*1 = 3. (End)
		

Links

• G. C. Greubel, Rows n = 0..100 of the triangle, flattened
• Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
• Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, JIS 24 (2021) 21.3.8.

Crossrefs

Cf. A000045, A001654 (row sums), A008967, A035317, A049310, A092879, A335964.

Programs

Magma

[(&+[(-1)^(j+n-k)*Binomial(2*k+j+1, j): j in [0..n-k]]): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 18 2021

Maple

T := (n,k) -> binomial(k+n+2, n-k+1)*hypergeom([1, k+n+3], [n-k+2], -1) + (-1)^(n-k)/4^(k+1):
seq(seq(simplify(T(n,k)), k=0..n), n=0..9); # Peter Luschny, Oct 31 2019

Mathematica

Table[Sum[(-1)^(j+n-k)*Binomial[j+2*k+1, j], {j,0,n-k}], {n,0,12}, {k,0,n}] // Flatten (* G. C. Greubel, Mar 18 2021 *)

Sage

flatten([[sum((-1)^(j+n-k)*binomial(j+2*k+1, j) for j in (0..n-k)) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Mar 18 2021

Formula

Sum_{k=0..n} T(n,k) = Fibonacci(n+1)*Fibonacci(n+2) = A001654(n+1).

From Johannes W. Meijer, Jul 20 2011: (Start)

T(n, k) = Sum_{i=0..n-k} (-1)^(i+n-k) * binomial(i+2*k+1, i).

T(n, k) = A035317(n+k, n-k) = A092879(n, n-k).

Sum_{k=0..n} T(n, k)*r^k = coeftayl(1/(1-(r+1)*x-(r+1)*x^2+x^3), x=0, n). [Barry] (End)

T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-2, k) + T(n-2, k-1) - T(n-3, k), T(0, 0) = 1, T(n, k) = 0 if k<0 or if k>n. - Philippe Deléham, Nov 12 2013

From Wolfdieter Lang, Oct 22 2019: (Start)

O.g.f. for the row polynomials (that is for the triangle): G(z, x) = 1/((1 + z)*(1 - (x + 2)*z + z^2)), and

O.g.f. for column k: x^k/((1+x)*(1-x)^(2*(k+1))) (Riordan property). (End)

T(n, k) = binomial(k + n + 2, n - k + 1)*hypergeom([1, k + n + 3], [n - k + 2], -1) + (-1)^(n - k)/4^(k + 1). - Peter Luschny, Oct 31 2019

From Michael A. Allen, Mar 20 2021: (Start)

T(n,k) = A335964(2*n+1,n-k).

T(n,k) = T(n-2,k) + binomial(n+k,2*k). (End)