A246609 Number T(n,k) of endofunctions on [n] whose cycle lengths are multiples of k; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

1, 0, 1, 0, 4, 1, 0, 27, 6, 2, 0, 256, 57, 24, 6, 0, 3125, 680, 300, 120, 24, 0, 46656, 9945, 4480, 2160, 720, 120, 0, 823543, 172032, 78750, 41160, 17640, 5040, 720, 0, 16777216, 3438673, 1591296, 866460, 430080, 161280, 40320, 5040

Offset

0,5

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k <= n. T(0,k) = 1, T(n,k) = 0 for k > n and n > 0.

Column k > 1 is asymptotic to n^(n - 1/2 + 1/(2*k)) * sqrt(2*Pi) / (2^(1/(2*k)) * k^(1/k) * Gamma(1/(2*k))) * (1 - (3*k-1)*(k-1) * sqrt(2/n) * Gamma(1/(2*k)) / (12 * k^2 * Gamma(1/2+1/(2*k)))). - Vaclav Kotesovec, Sep 01 2014

Links

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

Formula

E.g.f. for column k > 0: 1 / (1 - (-1)^k * LambertW(-x)^k)^(1/k). - Vaclav Kotesovec, Sep 01 2014

Example

Triangle T(n,k) begins:
  1;
  0,      1;
  0,      4,      1;
  0,     27,      6,     2;
  0,    256,     57,    24,     6;
  0,   3125,    680,   300,   120,    24;
  0,  46656,   9945,  4480,  2160,   720,  120;
  0, 823543, 172032, 78750, 41160, 17640, 5040, 720;
  ...

Maple

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

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0 || i > n, 0, Sum[b[n-i*j, i+k, k]*(i-1)!^j*multinomial[n, {n-i*j, Sequence @@ Table[i, {j}]}]/j!, {j, 0, n/i}]]]; T[0, 0] = 1; T[n_, k_] := Sum[b[j, k, k]*n^(n-j)*Binomial[n-1, j-1], {j, 0, n}]; 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, A000312, A060435, A246610, A246611, A246612, A246613, A246614, A246615, A246616, A246617.

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

T(2n,n) gives A246618.

Sequence in context: A081114 A069018 A156811 * A394436 A395929 A371080

Adjacent sequences: A246606 A246607 A246608 * A246610 A246611 A246612

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 31 2014

Status

approved