A100631 Triangle read by rows: T(n,k) = 2*(T(n-1,k-1) - T(n-2,k-1) + T(n-1,k)) for 0 < k < n, T(n,0) = T(n,n) = 1.

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 12, 8, 1, 1, 16, 32, 32, 16, 1, 1, 32, 80, 104, 80, 32, 1, 1, 64, 192, 304, 304, 192, 64, 1, 1, 128, 448, 832, 1008, 832, 448, 128, 1, 1, 256, 1024, 2176, 3072, 3072, 2176, 1024, 256, 1, 1, 512, 2304, 5504, 8832, 10272, 8832, 5504, 2304, 512, 1

Offset

0,5

Comments

From Petros Hadjicostas, Feb 09 2021: (Start)

The rectangular version (R(n,k): n,k >= 0) of this symmetric triangular array (T(n,k): 0 <= k <= n) is given by R(n,k) = T(n+k,k) for n,k >= 0. Conversely, T(n,k) = R(n-k, k) for 0 <= k <= n.

Note that [o.g.f of R](x,y) = [o.g.f. of T](x, y/x) and [o.g.f of T](x,y) = [o.g.f of R](x,x*y). (End)

From Petros Hadjicostas, Feb 10 2021: (Start)

All the conjectures below are true because one has to prove only one of them, and the rest follow from the proved one.

As Peter Luschny pointed out, one has to show only that the function S(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1) satisfies the recurrence S(n,k) = 2*(S(n,k-1) - S(n-1,k-1) + S(n-1,k)) for n, k > 0 and the initial conditions S(n,0) = S(0,n) = 1 for n >= 0.

This is quite easy to achieve because S(n,k) = 2^n*Sum_{s=0}^{k-1} binomial(k-1,s)*binomial(n+s-1,s) for n >= 0 and k >= 1. The proof of the recurrence relies on the identity binomial(m,n) = binomial(m-1, n) + binomial(m-1,n-1).

Note that without the 2^n in the formula R(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1), we essentially get array A049600.

In addition, note that without the 2^(n-k-1) in the formula T(n,k+1) = 2^(n-k-1)*hypergeom([-k, n-k+1], [1], -1), we essentially get A208341 (without the first column and the main diagonal of T). (End)

Links

Table of n, a(n) for n=0..65.

Index entries for triangles and arrays related to Pascal's triangle

Formula

From Petros Hadjicostas, Feb 09 2021: (Start)

Formulas for the triangular array (T(n,k): 0 <= k <= n):

T(n,k) = T(n,n-k) for 0 <= k <= n.

Sum_{k=0..n} T(n,k) = A087161(n+1).

T(n,1) = T(n,n-1) = 2^(n-1) = A000079(n-1) for n >= 1.

T(n,2) = T(n,n-2) = (n-1)*2^(n-2) = A001787(n-1) for n >= 2.

T(n,3) = T(n,n-3) = (n^2-n-4)*2^(n-4) = A100312(n-3) for n >= 3.

T(n,floor(n/2)) = T(n,ceiling(n/2)) = A341344(n).

Bivariate o.g.f.: Sum_{n,k >= 0} T(n,k)*x^n*y^k = (3*x^2*y - 2*x*y - 2*x + 1)/((1 - x)*(-x*y + 1)*(2*x^2*y - 2*x*y - 2*x + 1)).

Conjecture based on Peter Luschny's formulas in other sequences: T(n,k) = 2^(n-k)*hypergeom([-k + 1, n-k], [1], -1) = 2^k*hypergeom([-(n-k) + 1, k], [1], -1).

Formulas for the rectangular array (R(n,k): n,k >= 0):

R(n,k) = 2*(R(n,k-1) - R(n-1,k-1) + R(n-1,k)) for n,k > 0 with R(n,0) = R(0,n) = 1 for n >= 0.

R(n,k) = R(k, n) for n,k >= 0.

R(1,n) = R(n,1) = 2^n = A000079(n).

R(2,n) = R(n,2) = (n+1)*2^n = A001787(n+1).

R(3,n) = R(n,3) = (n^2+5*n+2)*2^(n-1) = A100312(n).

R(n,n) = A152254(n-1) = 2*A084773(n-1) for n >= 1.

Bivariate o.g.f.: Sum_{n,k >= 0} R(n,k)*x^n*y^k = (3*x*y - 2*x - 2*y - 1)/((1 - x)*(1 - y)*(2*x*y - 2*x - 2*y - 1)).

Conjecture based on Peter Luschny's formulas in other sequences: R(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1) = 2^k*hypergeom([-n + 1, k], [1], -1). (End)

From Petros Hadjicostas, Feb 10 2021: (Start)

The above conjecture is true (see the comments).

R(n,k) = 2^k*Sum_{s=0}^{n-1} binomial(n-1,s)*binomial(k+s-1,s) = 2^n*Sum_{s=0}^{k-1} binomial(k-1,s)*binomial(n+s-1,s) for n, k >= 1.

To get two binomial formulas for T(n,k), use the equation T(n,k) = R(n-k, k) for 1 <= k <= n and the above formulas for R(n,k). (End)

Example

From Petros Hadjicostas, Feb 09 2021: (Start)
Triangle T(n,k) (with rows n >= 0 and columns 0 <= k <= n) begins:
  1,
  1,   1,
  1,   2,    1,
  1,   4,    4,    1,
  1,   8,   12,    8,    1,
  1,  16,   32,   32,   16,    1,
  1,  32,   80,  104,   80,   32,    1,
  1,  64,  192,  304,  304,  192,   64,    1,
  1, 128,  448,  832, 1008,  832,  448,  128,   1,
  1, 256, 1024, 2176, 3072, 3072, 2176, 1024, 256, 1,
  ...
Rectangular array R(n,k) (with rows n >= 0 and columns k >= 0) begins:
  1,   1,    1,    1,     1,     1,      1,       1, ...
  1,   2,    4,    8,    16,    32,     64,     128, ...
  1,   4,   12,   32,    80,   192,    448,    1024, ...
  1,   8,   32,  104,   304,   832,   2176,    5504, ...
  1,  16,   80,  304,  1008,  3072,   8832,   24320, ...
  1,  32,  192,  832,  3072, 10272,  32064,   95104, ...
  1,  64,  448, 2176,  8832, 32064, 107712,  341504, ...
  1, 128, 1024, 5504, 24320, 95104, 341504, 1150592, ...
  ... (End)

Mathematica

T[_, 0] = T[n_, n_] = 1;
T[n_, k_] /; 0<k<n := T[n, k] = 2(T[n-1, k-1]-T[n-2, k-1]+T[n-1, k]);
T[_, _] = 0;
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 03 2021 *)

Crossrefs

Cf. A000079, A001787, A049600, A084773, A087161, A100312, A152254, A208341, A341344.

Sequence in context: A156006 A137854 A062715 * A154867 A064298 A256894

Adjacent sequences: A100628 A100629 A100630 * A100632 A100633 A100634

Keyword

nonn,tabl

Author

Reinhard Zumkeller, Dec 03 2004

Extensions

Offset changed by Petros Hadjicostas, Feb 09 2021

Status

approved