A091491 Triangle, read by rows, where the n-th diagonal is generated from the n-th row by the sum of the products of the n-th row terms with binomial coefficients.

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 8, 4, 1, 1, 23, 22, 13, 5, 1, 1, 65, 64, 41, 19, 6, 1, 1, 197, 196, 131, 67, 26, 7, 1, 1, 626, 625, 428, 232, 101, 34, 8, 1, 1, 2056, 2055, 1429, 804, 376, 144, 43, 9, 1, 1, 6918, 6917, 4861, 2806, 1377, 573, 197, 53, 10, 1

Offset

0,5

Comments

Row sums are A014137 (partial sums of Catalan numbers A000108). Columns equal the partial sums of the columns of the Catalan convolution triangle A033184. Columns include A014137, A014138, A001453.

Apart from the first column, any term is the partial sum of terms of the row above, when summing from the right. - Ralf Stephan, Apr 27 2004

Matrix inverse equals triangle A104402.

Riordan array (1/(1-x), x*c(x)) where c(x) is the g.f. of A000108. - Philippe Deléham, Nov 04 2009

Links

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened

Formula

T(n, k) = Sum_{j=0..n-k} T(n-k, j)*C(k+j-1, k-1).

G.f.: 2/(2-y*(1-sqrt(1-4*x)))/(1-x).

T(n, k) = T(n-1, k-1) + T(n, k+1) for n>0, with T(n, 0)=1.

Recurrence: for k>0, T(n, k) = Sum_{j=k..n} T(n-1, j). - Ralf Stephan, Apr 27 2004

T(n+2,2)= |A099324(n+2)|. - Philippe Deléham, Nov 25 2009

T(n,k) = k * Sum_{i=0..n-k} binomial(2*(n-i)-k-1, n-i-1)/(n-i) for k>0; T(n,0)=1. - Vladimir Kruchinin, Feb 07 2011

From Gary W. Adamson, Jul 26 2011: (Start)

The n-th row of the triangle is the top row of M^n, where M is the following infinite square production matrix in which a column of (1,0,0,0,...) is prepended to an infinite lower triangular matrix of all 1's and the rest zeros:

1, 1, 0, 0, 0, 0, ...

0, 1, 1, 0, 0, 0, ...

0, 1, 1, 1, 0, 0, ...

0, 1, 1, 1, 1, 0, ...

0, 1, 1, 1, 1, 1, ...

(End)

Sum_{k=0..n} T(n,k) = Sum_{j=0..n} A000108(j) = A014137(n). - G. C. Greubel, Apr 30 2021

Example

T(7,3) = T(4,0)*C(2,2) + T(4,1)*C(3,2) + T(4,2)*C(5,2) + T(4,3)*C(6,2) = (1)*1 + (4)*3 + (3)*6 + (1)*10 = 41.
Rows begin:
  1;
  1,     1;
  1,     2,     1;
  1,     4,     3,     1;
  1,     9,     8,     4,     1;
  1,    23,    22,    13,     5,     1;
  1,    65,    64,    41,    19,     6,    1;
  1,   197,   196,   131,    67,    26,    7,    1;
  1,   626,   625,   428,   232,   101,   34,    8,    1;
  1,  2056,  2055,  1429,   804,   376,  144,   43,    9,   1;
  1,  6918,  6917,  4861,  2806,  1377,  573,  197,   53,  10,  1;
  1, 23714, 23713, 16795,  9878,  5017, 2211,  834,  261,  64, 11,  1;
  1, 82500, 82499, 58785, 35072, 18277, 8399, 3382, 1171, 337, 76, 12, 1;
  ...
As to the production matrix M, top row of M^3 = [1, 4, 3, 1, 0, 0, 0, ...].

Mathematica

nmax = 11; t[n_, k_] := k*(2n-k-1)!*HypergeometricPFQ[{1, k-n, -n}, {k/2-n+1/2, k/2-n+1}, 1/4]/(n!*(n-k)!); t[_, 0] = 1; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)

Prog

(PARI) T(n, k)=if(k>n || n<0 || k<0, 0, if(k==0 || k==n, 1, sum(j=0, n-k, T(n-k, j)*binomial(k+j-1, k-1)); ); )
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(PARI) T(n, k)=local(X=x+x*O(x^n), Y=y+y*O(y^k)); polcoeff(polcoeff(2/(2-Y*(1-sqrt(1-4*X)))/(1-X), n, x), k, y)
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(PARI) T(n, k)=if(n<k || k<0, 0, if(n==k || k==0, 1, T(n-1, k-1)+T(n, k+1)))
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(Haskell)
a091491 n k = a091491_tabl !! n !! k
a091491_row n = a091491_tabl !! n
a091491_tabl = iterate (\row -> 1 : scanr1 (+) row) [1]
-- Reinhard Zumkeller, Jul 12 2012
(Magma)
A091491:= func< n, k | k eq 0 select 1 else k*(&+[Binomial(2*(n-j)-k-1, n-j-1)/(n-j): j in [0..n-k]]) >;
[A091491(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Apr 30 2021
(Sage)
def A091491(n, k): return 1 if (k==0) else k*sum(binomial(2*(n-j)-k-1, n-j-1)/(n-j) for j in (0..n-k))
flatten([[A091491(n, k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Apr 30 2021

Crossrefs

Cf. A000108, A001453, A014137, A014138, A033184, A104402.

Cf. A096465 (reversed).

Sequence in context: A339428 A204849 A105632 * A117418 A101494 A125781

Adjacent sequences: A091488 A091489 A091490 * A091492 A091493 A091494

Keyword

nonn,tabl

Author

Paul D. Hanna, Jan 14 2004

Status

approved