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,5

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.

Links

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

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

Example

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; ...

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 *)

Prog

(PARI) T(n, k)=if(n<k || k<0, 0, if(n==k, 1, (k+1)*T(n, k+1)-sum(j=1, n-k-1, T(j, 0)*T(n, j+k+1))))
(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(n<k || k<0, 0, if(k==0, 1, k*sum(j=k-1, n, j!)/(k+1)!)) \\ Paul D. Hanna, Jun 20 2006
(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
(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

Crossrefs

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

Sequence in context: A186020 A241579 A308292 * A125860 A294585 A283674

Adjacent sequences: A117393 A117394 A117395 * A117397 A117398 A117399

Keyword

nonn,tabl

Author

Paul D. Hanna, Mar 11 2006

Status

approved