login
Triangular array read by rows: T(n,k) is the number of n-permutations that have exactly k distinct cycle lengths.
8

%I #28 Jul 26 2018 16:59:33

%S 1,2,3,3,10,14,25,95,176,424,120,721,3269,1050,6406,21202,12712,42561,

%T 178443,141876,436402,1622798,1418400,151200,3628801,17064179,

%U 17061660,2162160,48073796,177093256,212254548,41580000,479001601,2293658861,2735287698,719072640

%N Triangular array read by rows: T(n,k) is the number of n-permutations that have exactly k distinct cycle lengths.

%C T(A000217(n),n) gives A246292. - _Alois P. Heinz_, Aug 21 2014

%H Alois P. Heinz, <a href="/A218868/b218868.txt">Rows n = 1..170, flattened</a>

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge University Press, 2009

%F E.g.f.: Product_{i>=1} (1 + y*exp(x^i/i) - y).

%e : 1;

%e : 2;

%e : 3, 3;

%e : 10, 14;

%e : 25, 95;

%e : 176, 424, 120;

%e : 721, 3269, 1050;

%e : 6406, 21202, 12712;

%e : 42561, 178443, 141876;

%e : 436402, 1622798, 1418400, 151200;

%p with(combinat):

%p b:= proc(n, i) option remember; expand(`if`(n=0, 1,

%p `if`(i<1, 0, add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*

%p b(n-i*j, i-1)*`if`(j=0, 1, x), j=0..n/i))))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n$2)):

%p seq(T(n), n=1..16); # _Alois P. Heinz_, Aug 21 2014

%t nn=10;a=Product[1-y+y Exp[x^i/i],{i,1,nn}];f[list_]:=Select[list,#>0&];Map[f,Drop[Range[0,nn]!CoefficientList[Series[a ,{x,0,nn}],{x,y}],1]]//Grid

%Y Columns k=1-3 give: A005225, A005772, A133119.

%Y Row sums are: A000142.

%Y Row lengths are: A003056.

%Y Cf. A208437, A242027 (the same for endofunctions), A246292, A317327.

%K nonn,tabf

%O 1,2

%A _Geoffrey Critzer_, Nov 07 2012