|
%I #17 May 05 2019 08:58:23
%S 1,1,1,1,1,1,1,1,4,1,1,1,3,27,1,1,1,4,12,256,1,1,1,3,19,100,3125,1,1,
%T 1,4,12,116,1075,46656,1,1,1,3,21,73,985,13356,823543,1,1,1,4,10,148,
%U 580,11026,197764,16777216,1,1,1,3,21,44,1281,5721,145621,3403576,387420489,1
%N Number A(n,k) of endofunctions on [n] that are the k-th power of an endofunction; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C Number of endofunctions f on [n] such that an endofunction g on [n] exists with f=g^k.
%e A(3,2) = 12: (1,1,1), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,3), (2,2,2), (2,2,3), (2,3,1), (3,1,2), (3,2,3), (3,3,3).
%e A(3,6) = 10: (1,1,1), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,3), (2,2,2), (2,2,3), (3,2,3), (3,3,3).
%e A(4,4) = 73: (1,1,1,1), (1,1,1,4), (1,1,3,1), (1,1,3,3), ..., (4,4,1,3), (4,4,2,3), (4,4,3,4), (4,4,4,4).
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 4, 3, 4, 3, 4, 3, 4, ...
%e 1, 27, 12, 19, 12, 21, 10, 21, ...
%e 1, 256, 100, 116, 73, 148, 44, 148, ...
%e 1, 3125, 1075, 985, 580, 1281, 295, 1305, ...
%e 1, 46656, 13356, 11026, 5721, 12942, 3136, 13806, ...
%e 1, 823543, 197764, 145621, 69244, 150955, 42784, 169681, ...
%t (* This program is not suitable to compute a large number of terms. *)
%t nmax = 8;
%t f[a_][b_] /; Length[a]==Length[b] := Table[b[[a[[i]]]], {i, 1, Length[a]}];
%t A[n_, k_] := Nest[f[#], Range[n], k]& /@ Tuples[Range[n], {n}] // Union // Length;
%t Table[A[n-k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* _Jean-François Alcover_, May 05 2019 *)
%Y Columns k=0-10 give: A000012, A000312, A102687, A163859, A163860, A163861, A247053, A247054, A247055, A247056, A247057.
%Y Rows n=0+1, 2-7 give: A000012, A103947, A103948, A103949, A102709, A103950, A247058.
%Y Main diagonal gives A247059.
%Y Cf. A247005 (the same for permutations).
%K nonn,tabl
%O 0,9
%A _Alois P. Heinz_, Sep 09 2014
|
