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

%I #46 Oct 17 2022 07:22:26

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

%T 1,0,5040,2208,828,272,70,12,1,0,40320,14976,4968,1576,440,96,14,1,0,

%U 362880,115200,33192,9696,2720,664,126,16,1,0,3628800,996480,247968,64704,17312,4380,952,160,18,1

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

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

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

%C Also the convolution triangle of the factorial numbers for n >= 1. - _Peter Luschny_, Oct 09 2022

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

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

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

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

%F Sum_{k=0..n} T(n, k)*binomial(m, k) = A084938(m+n, m). - _Philippe Deléham_, Jan 31 2004

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

%F From _Peter Bala_, May 27 2017: (Start)

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

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

%e Triangle begins:

%e 1;

%e 0, 1;

%e 0, 2, 1;

%e 0, 6, 4, 1;

%e 0, 24, 16, 6, 1;

%e 0, 120, 72, 30, 8, 1;

%e 0, 720, 372, 152, 48, 10, 1;

%e 0, 5040, 2208, 828, 272, 70, 12, 1;

%e 0, 40320, 14976, 4968, 1576, 440, 96, 14, 1;

%e 0, 366880, 115200, 33192, 9696, 2720, 664, 126, 16, 1;

%e 0, 3628800, 996480, 247968, 64704, 17312, 4380, 952, 160, 18, 1;

%e ...

%p T := proc(n,k) option remember; if n=0 and k=0 then return 1 fi;

%p if n>0 and k=0 or k>0 and n=0 then return 0 fi;

%p T(n-1,k-1)+(n+k-1)*T(n-1,k)/k end:

%p for n from 0 to 10 do seq(T(n,k),k=0..n) od; # _Peter Luschny_, Mar 03 2016

%p # Uses function PMatrix from A357368.

%p PMatrix(10, factorial); # _Peter Luschny_, Oct 09 2022

%t 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;

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jun 20 2018 *)

%Y Another version: A059369.

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

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

%Y Cf. A084938.

%K easy,nonn,tabl

%O 0,5

%A _Philippe Deléham_, Jan 23 2004, Jun 14 2007

%E New name using a comment from _David Callan_ by _Peter Luschny_, Sep 01 2022