A163860 -id:A163860 - cp's OEIS frontend

A247026 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.

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, 1, 4, 12, 116, 1075, 46656, 1, 1, 1, 3, 21, 73, 985, 13356, 823543, 1, 1, 1, 4, 10, 148, 580, 11026, 197764, 16777216, 1, 1, 1, 3, 21, 44, 1281, 5721, 145621, 3403576, 387420489, 1

Offset: 0

Alois P. Heinz, Sep 09 2014

Number of endofunctions f on [n] such that an endofunction g on [n] exists with f=g^k.

			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).
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).
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).
Square array A(n,k) begins:
  1,      1,      1,      1,     1,      1,     1,      1, ...
  1,      1,      1,      1,     1,      1,     1,      1, ...
  1,      4,      3,      4,     3,      4,     3,      4, ...
  1,     27,     12,     19,    12,     21,    10,     21, ...
  1,    256,    100,    116,    73,    148,    44,    148, ...
  1,   3125,   1075,    985,   580,   1281,   295,   1305, ...
  1,  46656,  13356,  11026,  5721,  12942,  3136,  13806, ...
  1, 823543, 197764, 145621, 69244, 150955, 42784, 169681, ...

Columns k=0-10 give: A000012, A000312, A102687, A163859, A163860, A163861, A247053, A247054, A247055, A247056, A247057.
Rows n=0+1, 2-7 give: A000012, A103947, A103948, A103949, A102709, A103950, A247058.
Main diagonal gives A247059.
Cf. A247005 (the same for permutations).

(* This program is not suitable to compute a large number of terms. *)
nmax = 8;
f[a_][b_] /; Length[a]==Length[b] := Table[b[[a[[i]]]], {i, 1, Length[a]}];
A[n_, k_] := Nest[f[#], Range[n], k]& /@ Tuples[Range[n], {n}] // Union // Length;
Table[A[n-k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, May 05 2019 *)

A163947 Number of functions on a finite set that are not obtainable by any composition power (excluding identity as power).

Original entry on oeis.org

0, 0, 6, 84, 1400, 25590, 516432

Offset: 1

Carlos Alves, Aug 06 2009

a(n) is the number of functions on a finite set {1,...,n} that are not composition powers of any other function or powers(>1) of itself.

Hard to compute for n>7, as the number of functions to test is n^n.

			For n=2, the set is {1,2} and we have 4 functions: the constants 1 and 2, the identity, and the transposition. Any composition power of a constant function or of identity is the function itself. Odd composition powers of the transposition give the transposition. Thus all 4 functions are represented.
For n=3, the set is {1,2,3} and f:{1,2,3}->{1,1,2} cannot be represented by composition powers of any other function, or powers of itself (as fof gives the constant function=1). There are 6 functions in this situation (similar).

Cf. A102687, A163859, A163860, A163861, A163948.

a(n) = n^n - A163948(n).

A163861 Number of different 5th-power (quintic) mappings of a finite set of n elements into itself.

Original entry on oeis.org

1, 1, 4, 21, 148, 1281, 12942, 150955, 2042272, 31912425, 567737326

Offset: 0

Carlos Alves, Aug 05 2009

The same as A102687 (square composition), A163859 (cubic composition), A163860 (4th-power composition), here a(n) is the number of different mappings g that admit at least one mapping f as the 5th-order root (g=fofofofof) in terms of the composition.

Cf. A102687, A163859, A163860.

Column k=5 of A247026.

a(0) from Alois P. Heinz, Sep 09 2014

a(8)-a(10) from Bert Dobbelaere, Jan 24 2019

A163948 The number of functions on a finite set that are obtainable by a composition power (excluding identity as power).

Original entry on oeis.org

1, 4, 21, 172, 1725, 21066, 307111

Offset: 1

Carlos Alves, Aug 06 2009

The complementary set to A163947.

Cf. A163947, see also A102687, A163859, A163860, A163861.

a(n) = n^n - A163947(n).

cp's OEIS Frontend

A247026 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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A163947 Number of functions on a finite set that are not obtainable by any composition power (excluding identity as power).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A163861 Number of different 5th-power (quintic) mappings of a finite set of n elements into itself.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A163948 The number of functions on a finite set that are obtainable by a composition power (excluding identity as power).

Views

Author

Keywords

Comments

Crossrefs

Formula