cp's OEIS Frontend

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

%I A241981 #34 Dec 16 2021 16:44:05
%S A241981 1,0,1,0,3,1,0,16,9,2,0,125,93,32,6,0,1296,1155,500,150,24,0,16807,
%T A241981 17025,8600,3240,864,120,0,262144,292383,165690,72030,24696,5880,720,
%U A241981 0,4782969,5752131,3568768,1719060,688128,215040,46080,5040
%N A241981 Number T(n,k) of endofunctions on [n] where the largest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C A241981 T(0,0) = 1 by convention.
%C A241981 In general, number of endofunctions on [n] where the largest cycle length equals k is asymptotic to (k*exp(H(k)) - (k-1)*exp(H(k-1))) * n^(n-1), where H(k) is the harmonic number A001008/A002805, k>=1. The multiplicative constant is (for big k) asymptotic to 2*k*exp(gamma), where gamma is the Euler-Mascheroni constant (see A001620 and A073004). - _Vaclav Kotesovec_, Aug 21 2014
%H A241981 Alois P. Heinz, <a href="/A241981/b241981.txt">Rows n = 0..140, flattened</a>
%e A241981 Triangle T(n,k) begins:
%e A241981   1;
%e A241981   0,      1;
%e A241981   0,      3,      1;
%e A241981   0,     16,      9,      2;
%e A241981   0,    125,     93,     32,     6;
%e A241981   0,   1296,   1155,    500,   150,    24;
%e A241981   0,  16807,  17025,   8600,  3240,   864,  120;
%e A241981   0, 262144, 292383, 165690, 72030, 24696, 5880, 720;
%e A241981   ...
%p A241981 with(combinat):
%p A241981 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A241981       add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
%p A241981       b(n-i*j, i-1), j=0..n/i)))
%p A241981     end:
%p A241981 A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
%p A241981 T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
%p A241981 seq(seq(T(n, k), k=0..n), n=0..10);
%t A241981 multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i-1)!^j*multinomial[n, {n-i*j, Sequence @@ Table[i, {j}]}]/j!*b[n-i*j, i-1], {j, 0, n/i}]]]; A[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}]; T[0, 0] = 1; T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Jan 06 2015, after _Alois P. Heinz_ *)
%Y A241981 Columns k=0-10 give: A000007, A000272(n+1) for n>0, A163951, A246213, A246214, A246215, A246216, A246217, A246218, A246219, A246220.
%Y A241981 T(2n,n) gives A241982.
%Y A241981 Row sums give A000312.
%Y A241981 Main diagonal gives A000142(n-1) for n>0.
%Y A241981 Cf. A246049, A243098.
%K A241981 nonn,tabl
%O A241981 0,5
%A A241981 _Alois P. Heinz_, Aug 10 2014