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.

1, 0, 1, 0, 3, 1, 0, 19, 6, 2, 0, 175, 51, 24, 6, 0, 2101, 580, 300, 120, 24, 0, 31031, 8265, 4360, 2160, 720, 120, 0, 543607, 141246, 74130, 41160, 17640, 5040, 720, 0, 11012415, 2810437, 1456224, 861420, 430080, 161280, 40320, 5040

Offset

0,5

Comments

T(0,0) = 1 by convention.

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

Links

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

Example

Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     19,      6,     2;
  0,    175,     51,    24,     6;
  0,   2101,    580,   300,   120,    24;
  0,  31031,   8265,  4360,  2160,   720,  120;
  0, 543607, 141246, 74130, 41160, 17640, 5040, 720;
  ...

Maple

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), A(n, k) -A(n, k+1)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i>n, 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, k], {j, 0, n}];
T[n_, k_] := If[k == 0, If[n == 0, 1, 0], A[n, k] - A[n, k+1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 06 2015, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A045531, A246189, A246190, A246191, A246192, A246193, A246194, A246195, A246196, A246197.

T(2n,n) gives A246050.

Row sums give A000312.

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

Cf. A241981, A243098.

Sequence in context: A241981 A147723 A110518 * A316773 A006837 A158782

Adjacent sequences: A246046 A246047 A246048 * A246050 A246051 A246052

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 11 2014

Status

approved