login
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.
9

%I #50 Jun 05 2021 16:41:01

%S 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,

%T 196,131,67,26,7,1,1,626,625,428,232,101,34,8,1,1,2056,2055,1429,804,

%U 376,144,43,9,1,1,6918,6917,4861,2806,1377,573,197,53,10,1

%N 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.

%C 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.

%C 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

%C Matrix inverse equals triangle A104402.

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

%H Reinhard Zumkeller, <a href="/A091491/b091491.txt">Rows n=0..150 of triangle, flattened</a>

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

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

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

%F Recurrence: for k>0, T(n, k) = Sum_{j=k..n} T(n-1, j). - _Ralf Stephan_, Apr 27 2004

%F T(n+2,2)= |A099324(n+2)|. - _Philippe Deléham_, Nov 25 2009

%F 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

%F From _Gary W. Adamson_, Jul 26 2011: (Start)

%F 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:

%F 1, 1, 0, 0, 0, 0, ...

%F 0, 1, 1, 0, 0, 0, ...

%F 0, 1, 1, 1, 0, 0, ...

%F 0, 1, 1, 1, 1, 0, ...

%F 0, 1, 1, 1, 1, 1, ...

%F (End)

%F Sum_{k=0..n} T(n,k) = Sum_{j=0..n} A000108(j) = A014137(n). - _G. C. Greubel_, Apr 30 2021

%e 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.

%e Rows begin:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 4, 3, 1;

%e 1, 9, 8, 4, 1;

%e 1, 23, 22, 13, 5, 1;

%e 1, 65, 64, 41, 19, 6, 1;

%e 1, 197, 196, 131, 67, 26, 7, 1;

%e 1, 626, 625, 428, 232, 101, 34, 8, 1;

%e 1, 2056, 2055, 1429, 804, 376, 144, 43, 9, 1;

%e 1, 6918, 6917, 4861, 2806, 1377, 573, 197, 53, 10, 1;

%e 1, 23714, 23713, 16795, 9878, 5017, 2211, 834, 261, 64, 11, 1;

%e 1, 82500, 82499, 58785, 35072, 18277, 8399, 3382, 1171, 337, 76, 12, 1;

%e ...

%e As to the production matrix M, top row of M^3 = [1, 4, 3, 1, 0, 0, 0, ...].

%t 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_ *)

%o (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)););)

%o for(n=0,10,for(k=0,n,print1(T(n,k),", "));print(""))

%o (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)

%o for(n=0,10,for(k=0,n,print1(T(n,k),", "));print(""))

%o (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)))

%o for(n=0,10,for(k=0,n,print1(T(n,k),", "));print(""))

%o (Haskell)

%o a091491 n k = a091491_tabl !! n !! k

%o a091491_row n = a091491_tabl !! n

%o a091491_tabl = iterate (\row -> 1 : scanr1 (+) row) [1]

%o -- _Reinhard Zumkeller_, Jul 12 2012

%o (Magma)

%o 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]]) >;

%o [A091491(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Apr 30 2021

%o (Sage)

%o 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))

%o flatten([[A091491(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, Apr 30 2021

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

%Y Cf. A096465 (reversed).

%K nonn,tabl

%O 0,5

%A _Paul D. Hanna_, Jan 14 2004