A245980 Number A(n,k) of pairs of endofunctions f, g on [n] satisfying g^k(f(i)) = f(i) for all i in [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 16, 1, 1, 6, 729, 1, 1, 10, 87, 65536, 1, 1, 6, 213, 2200, 9765625, 1, 1, 10, 141, 8056, 84245, 2176782336, 1, 1, 6, 213, 6184, 465945, 4492656, 678223072849, 1, 1, 10, 87, 9592, 387545, 37823616, 315937195, 281474976710656

Offset

0,6

Links

Alois P. Heinz, Antidiagonals n = 0..80, flattened

Example

Square array A(n,k) begins:
0 :        1,     1,      1,      1,      1,      1, ...
1 :        1,     1,      1,      1,      1,      1, ...
2 :       16,     6,     10,      6,     10,      6, ...
3 :      729,    87,    213,    141,    213,     87, ...
4 :    65536,  2200,   8056,   6184,   9592,   2200, ...
5 :  9765625, 84245, 465945, 387545, 682545, 159245, ...

Maple

with(numtheory): with(combinat): M:=multinomial:
b:= proc(n, k, p) local l, g; l, g:= sort([divisors(p)[]]),
      proc(k, m, i, t) option remember; local d, j; d:= l[i];
        `if`(i=1, n^m, add(M(k, k-(d-t)*j, (d-t)$j)/j!*
         (d-1)!^j *M(m, m-t*j, t$j) *g(k-(d-t)*j, m-t*j,
        `if`(d-t=1, [i-1, 0], [i, t+1])[]), j=0..min(k/(d-t),
        `if`(t=0, [][], m/t))))
      end; g(k, n-k, nops(l), 0)
    end:
A:= (n, k)-> `if`(k=0, n^(2*n), add(b(n, j, k)*
             stirling2(n, j)*binomial(n, j)*j!, j=0..n)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!); M = multinomial;
b[n_, k0_, p_] := Module[{l, g}, l = Sort[Divisors[p]]; g[k_, m_, i_, t_] := g[k, m, i, t] = Module[{d, j}, d = l[[i]]; If[i == 1, n^m, Sum[M[k, Join[{k - (d-t)*j}, Array[(d - t)&, j]]]/ j!*(d-1)!^j * M[m, Join[{m - t*j}, Array[t&, j]]]*If[d-t == 1, g[k - (d - t)*j, m - t*j, i-1, 0], g[k - (d-t)*j, m - t*j, i, t+1]], {j, 0, Min[k/(d-t), If[t == 0, Infinity, m/t]]}]]]; g[k0, n-k0, Length[l], 0]];
A[n_, k_] := If[k == 0, n^(2*n), Sum[b[n, j, k]*StirlingS2[n, j]* Binomial[n, j]*j!, {j, 0, n}]]; A[0, _] = 1; A[1, _] = 1;
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A062206, A239750, A239771, A241015, A245981, A245982, A245983, A245984, A245985, A245986, A245987.

Main diagonal gives A245988.

Cf. A245910.

Sequence in context: A361132 A040258 A040257 * A040256 A245910 A133824

Adjacent sequences: A245977 A245978 A245979 * A245981 A245982 A245983

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 08 2014

Status

approved