login
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.
11

%I #31 Sep 23 2022 16:21:41

%S 1,0,1,0,4,1,0,27,6,2,0,256,57,24,6,0,3125,680,300,120,24,0,46656,

%T 9945,4480,2160,720,120,0,823543,172032,78750,41160,17640,5040,720,0,

%U 16777216,3438673,1591296,866460,430080,161280,40320,5040

%N 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.

%C 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.

%C 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

%H Alois P. Heinz, <a href="/A246609/b246609.txt">Rows n = 0..140, flattened</a>

%F E.g.f. for column k > 0: 1 / (1 - (-1)^k * LambertW(-x)^k)^(1/k). - _Vaclav Kotesovec_, Sep 01 2014

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 4, 1;

%e 0, 27, 6, 2;

%e 0, 256, 57, 24, 6;

%e 0, 3125, 680, 300, 120, 24;

%e 0, 46656, 9945, 4480, 2160, 720, 120;

%e 0, 823543, 172032, 78750, 41160, 17640, 5040, 720;

%e ...

%p with(combinat):

%p b:= proc(n, i, k) option remember; `if`(n=0, 1,

%p `if`(i=0 or i>n, 0, add(b(n-i*j, i+k, k)*(i-1)!^j*

%p multinomial(n, n-i*j, i$j)/j!, j=0..n/i)))

%p end:

%p T:= (n, k)->add(b(j, k$2)*n^(n-j)*binomial(n-1, j-1), j=0..n):

%p seq(seq(T(n,k), k=0..n), n=0..10);

%t 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_ *)

%Y Columns k=0-10 give: A000007, A000312, A060435, A246610, A246611, A246612, A246613, A246614, A246615, A246616, A246617.

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

%Y T(2n,n) gives A246618.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Aug 31 2014