A117396 Triangle, read by rows, defined by: T(n,k) = (k+1)*T(n,k+1) - Sum_{j=1..n-k-1} T(j,0)*T(n,j+k+1) for n>k with T(n,n)=1 for n>=0.

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 17, 11, 4, 1, 1, 77, 51, 19, 5, 1, 1, 437, 291, 109, 29, 6, 1, 1, 2957, 1971, 739, 197, 41, 7, 1, 1, 23117, 15411, 5779, 1541, 321, 55, 8, 1, 1, 204557, 136371, 51139, 13637, 2841, 487, 71, 9, 1, 1, 2018957, 1345971, 504739, 134597, 28041, 4807, 701, 89, 10, 1

Offset: 0

Author

Paul D. Hanna, Mar 11 2006

Keywords

• nonn
• tabl

Comments

Columns equal the partial sums of columns of triangle A092582 for k>0: T(n, k) - T(n-1, k) = A092582(n,k) = number of permutations p of [n] having length of first run equal to k.

Examples

			Triangle begins:
  1;
  1,      1;
  1,      2,      1;
  1,      5,      3,     1;
  1,     17,     11,     4,     1;
  1,     77,     51,    19,     5,    1;
  1,    437,    291,   109,    29,    6,   1;
  1,   2957,   1971,   739,   197,   41,   7,  1;
  1,  23117,  15411,  5779,  1541,  321,  55,  8, 1;
  1, 204557, 136371, 51139, 13637, 2841, 487, 71, 9, 1; ...
Matrix inverse is:
   1;
  -1,  1;
   1, -2,  1;
   1,  1, -3,  1;
   1,  1,  1, -4,  1;
   1,  1,  1,  1, -5, 1; ...
Matrix log is the integer triangle A117398:
    0;
    1,  0;
    0,  2,  0;
   -1,  2,  3,  0;
   -3,  4,  5,  4,  0;
   -9, 14, 15,  9,  5,  0;
  -33, 68, 65, 34, 14,  6,  0; ...
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Crossrefs

Cf. A014288 (column 1), A056199 (column 2), A117397 (column 3), A003422 (row sums), A117398 (matrix log); A092582.

Programs

Magma

[k eq 0 select 1 else k*(&+[Factorial(j)/Factorial(k+1): j in [k-1..n]]): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 24 2021

Mathematica

T[n_, k_]:= T[n, k]= If[k==0, 1, k*Sum[j!/(k+1)!, {j,k-1,n}]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 24 2021 *)

PARI

T(n,k)=if(n
				

PARI

/* Definition by Matrix Inverse: */ T(n,k)=local(M=matrix(n+1,n+1,r,c,if(r>=c,if(r==c+1,-c,1))));(M^-1)[n+1,k+1]

PARI

T(n,k)=if(nPaul D. Hanna, Jun 20 2006

Sage

def A117396(n,k): return 1 if (k==0) else k*sum(factorial(j)/factorial(k+1) for j in (k-1..n))
flatten([[A117396(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Sep 24 2021

Formula

T(n,k) = k*Sum_{j=k-1..n} j!/(k+1)! for n >= k > 0, with T(n,0) = 1 for n >= 0. - Paul D. Hanna, Jun 20 2006