A090238 Triangle T(n, k) read by rows. T(n, k) is the number of lists of k unlabeled permutations whose total length is n.

1, 0, 1, 0, 2, 1, 0, 6, 4, 1, 0, 24, 16, 6, 1, 0, 120, 72, 30, 8, 1, 0, 720, 372, 152, 48, 10, 1, 0, 5040, 2208, 828, 272, 70, 12, 1, 0, 40320, 14976, 4968, 1576, 440, 96, 14, 1, 0, 362880, 115200, 33192, 9696, 2720, 664, 126, 16, 1, 0, 3628800, 996480, 247968, 64704, 17312, 4380, 952, 160, 18, 1

Offset: 0

Author

Philippe Deléham, Jan 23 2004, Jun 14 2007

Keywords

• easy
• nonn
• tabl

Comments

T(n,k) is the number of lists of k unlabeled permutations whose total length is n. Unlabeled means each permutation is on an initial segment of the positive integers. Example: with dashes separating permutations, T(3,2) = 4 counts 1-12, 1-21, 12-1, 21-1. - David Callan, Nov 29 2007

For n > 0, -Sum_{i=0..n} (-1)^i*T(n,i) is the number of indecomposable permutations A003319. - Peter Luschny, Mar 13 2009

Also the convolution triangle of the factorial numbers for n >= 1. - Peter Luschny, Oct 09 2022

Examples

			Triangle begins:
  1;
  0,       1;
  0,       2,      1;
  0,       6,      4,      1;
  0,      24,     16,      6,     1;
  0,     120,     72,     30,     8,     1;
  0,     720,    372,    152,    48,    10,     1;
  0,    5040,   2208,    828,   272,    70,    12,    1;
  0,   40320,  14976,   4968,  1576,   440,    96,   14,   1;
  0,  366880, 115200,  33192,  9696,  2720,   664,  126,  16,   1;
  0, 3628800, 996480, 247968, 64704, 17312,  4380,  952, 160,  18,  1;
  ...
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 171, #34.

Crossrefs

Another version: A059369.

Row sums: A051296, A003319 (n>0).

Diagonals: A000007, A000142, A059371, A000012, A005843, A054000.

Cf. A084938.

Programs

Maple

T := proc(n,k) option remember; if n=0 and k=0 then return 1 fi;
if n>0 and k=0 or k>0 and n=0 then return 0 fi;
T(n-1,k-1)+(n+k-1)*T(n-1,k)/k end:
for n from 0 to 10 do seq(T(n,k),k=0..n) od; # Peter Luschny, Mar 03 2016
# Uses function PMatrix from A357368.
PMatrix(10, factorial); # Peter Luschny, Oct 09 2022

Mathematica

T[n_, k_] := T[n, k] = T[n-1, k-1] + ((n+k-1)/k)*T[n-1, k]; T[0, 0] = 1; T[, 0] = T[0, ] = 0;
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2018 *)

Formula

T(n, k) is given by [0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

T(n, k) = T(n-1, k-1) + ((n+k-1)/k)*T(n-1, k); T(0, 0)=1, T(n, 0)=0 if n > 0, T(0, k)=0 if k > 0.

G.f. for the k-th column: (Sum_{i>=1} i!*t^i)^k = Sum_{n>=k} T(n, k)*t^n.

Sum_{k=0..n} T(n, k)*binomial(m, k) = A084938(m+n, m). - Philippe Deléham, Jan 31 2004

T(n, k) = Sum_{j>=0} A090753(j)*T(n-1, k+j-1). - Philippe Deléham, Feb 18 2004

From Peter Bala, May 27 2017: (Start)

Conjectural o.g.f.: 1/(1 + t - t*F(x)) = 1 + t*x + (2*t + t^2)*x^2 + (6*t + 4*t^2 + t^3)*x^3 + ..., where F(x) = Sum_{n >= 0} n!*x^n.

If true then a continued fraction representation of the o.g.f. is 1 - t + t/(1 - x/(1 - t*x - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - 4*x/(1 - 4*x/(1 - ... ))))))))). (End)

Extensions

New name using a comment from David Callan by Peter Luschny, Sep 01 2022