cp's OEIS Frontend

A246049 Number T(n,k) of endofunctions on [n] where the smallest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%I A246049 #25 Jan 05 2021 21:38:25
%S A246049 1,0,1,0,3,1,0,19,6,2,0,175,51,24,6,0,2101,580,300,120,24,0,31031,
%T A246049 8265,4360,2160,720,120,0,543607,141246,74130,41160,17640,5040,720,0,
%U A246049 11012415,2810437,1456224,861420,430080,161280,40320,5040
%N A246049 Number T(n,k) of endofunctions on [n] where the smallest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C A246049 T(0,0) = 1 by convention.
%C A246049 In general, number of endofunctions on [n] where the smallest cycle length equals k is asymptotic to (exp(-H(k-1)) - exp(-H(k))) * n^n, where H(k) is the harmonic number A001008/A002805, k>=1. - _Vaclav Kotesovec_, Aug 21 2014
%H A246049 Alois P. Heinz, <a href="/A246049/b246049.txt">Rows n = 0..140, flattened</a>
%e A246049 Triangle T(n,k) begins:
%e A246049   1;
%e A246049   0,      1;
%e A246049   0,      3,      1;
%e A246049   0,     19,      6,     2;
%e A246049   0,    175,     51,    24,     6;
%e A246049   0,   2101,    580,   300,   120,    24;
%e A246049   0,  31031,   8265,  4360,  2160,   720,  120;
%e A246049   0, 543607, 141246, 74130, 41160, 17640, 5040, 720;
%e A246049   ...
%p A246049 with(combinat):
%p A246049 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 0,
%p A246049       add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
%p A246049       b(n-i*j, i+1), j=0..n/i)))
%p A246049     end:
%p A246049 A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, k), j=0..n):
%p A246049 T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), A(n, k) -A(n, k+1)):
%p A246049 seq(seq(T(n, k), k=0..n), n=0..12);
%t A246049 multinomial[n_, k_List] := n!/Times @@ (k!);
%t A246049 b[n_, i_] := b[n, i] = If[n == 0, 1, If[i>n, 0,
%t A246049       Sum[(i-1)!^j*multinomial[n, {n-i*j, Sequence @@ Table[i, {j}]}]/j!*
%t A246049       b[n-i*j, i+1], {j, 0, n/i}]]];
%t A246049 A[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, k], {j, 0, n}];
%t A246049 T[n_, k_] := If[k == 0, If[n == 0, 1, 0], A[n, k] - A[n, k+1]];
%t A246049 Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Jan 06 2015, after _Alois P. Heinz_ *)
%Y A246049 Columns k=0-10 give: A000007, A045531, A246189, A246190, A246191, A246192, A246193, A246194, A246195, A246196, A246197.
%Y A246049 T(2n,n) gives A246050.
%Y A246049 Row sums give A000312.
%Y A246049 Main diagonal gives A000142(n-1) for n>0.
%Y A246049 Cf. A241981, A243098.
%K A246049 nonn,tabl
%O A246049 0,5
%A A246049 _Alois P. Heinz_, Aug 11 2014