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.

1, 0, 1, 0, 3, 1, 0, 16, 9, 2, 0, 125, 93, 32, 6, 0, 1296, 1155, 500, 150, 24, 0, 16807, 17025, 8600, 3240, 864, 120, 0, 262144, 292383, 165690, 72030, 24696, 5880, 720, 0, 4782969, 5752131, 3568768, 1719060, 688128, 215040, 46080, 5040

Offset

0,5

Comments

T(0,0) = 1 by convention.

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

Links

Alois P. Heinz, Rows n = 0..140, flattened

Example

Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     16,      9,      2;
  0,    125,     93,     32,     6;
  0,   1296,   1155,    500,   150,    24;
  0,  16807,  17025,   8600,  3240,   864,  120;
  0, 262144, 292383, 165690, 72030, 24696, 5880, 720;
  ...

Maple

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

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

Crossrefs

Columns k=0-10 give: A000007, A000272(n+1) for n>0, A163951, A246213, A246214, A246215, A246216, A246217, A246218, A246219, A246220.

T(2n,n) gives A241982.

Row sums give A000312.

Main diagonal gives A000142(n-1) for n>0.

Cf. A246049, A243098.

Sequence in context: A114151 A243098 A360177 * A147723 A110518 A246049

Adjacent sequences: A241978 A241979 A241980 * A241982 A241983 A241984

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 10 2014

Status

approved