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

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

References

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

Links

Table of n, a(n) for n=0..65.

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)

Example

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

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

Crossrefs

Another version: A059369.

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

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

Cf. A084938.

Sequence in context: A205813 A127631 A122538 * A358694 A047922 A276891

Adjacent sequences: A090235 A090236 A090237 * A090239 A090240 A090241

Keyword

easy,nonn,tabl

Author

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

Extensions

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

Status

approved