A163859 -id:A163859 - 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).

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

Original entry on oeis.org

0, 0, 1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175, 4606094297461892895, 199122610252964803857, 9139190793845641425261, 443881600924216704982425

Offset: 0

Carlos Alves, Aug 06 2009

nonn

The number of functions in a finite set {1,..,n} for which the sequence of composition powers ends in a fixed point gave terms of the sequence A000272(n-1)=(n+1)^(n-1).

This is to be seen as a conjecture, and the sequence ending with a length 2 cycle does not seem to have such an easy expression.

			Any transposition (or disjoint combination) is one element to be counted.
When n=2, there is only one, and a(2)=1. When n=3, there are only 3 transpositions, but there are other 6 elements, for instance
f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),
(the others are similar), thus giving a(3)=9.

Alois P. Heinz, Table of n, a(n) for n = 0..387

Cf. A163947, A163952, A163859.

Column k=2 of A222029 and of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 2) -A(n, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 19 2014

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i - 1)!^j*multinomial[ n, Join[{n - i*j}, Table[i, j]]]/j!*b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] :=  Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
a[0] = 0; a[n_] := A[n, 2] - A[n, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)

a(n) ~ (2*exp(3/2)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 20 2014

a(0), a(8)-a(19) added and A246212 merged into this sequence by Alois P. Heinz, Aug 14 2017

A163860 Number of different 4th-power (quartic) mappings of a finite set of n elements into itself.

Original entry on oeis.org

1, 1, 3, 12, 73, 580, 5721, 69244, 1000210, 16319601, 297453340

Offset: 0

Carlos Alves, Aug 05 2009

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

Cf. A102687, A163859.

Column k=4 of A247026.

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

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

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

A163952 The number of functions in a finite set for which the sequence of composition powers ends in a length 3 cycle.

Original entry on oeis.org

0, 0, 0, 2, 32, 480, 7880, 145320, 3009888, 69554240, 1779185360, 49995179520, 1532580072320, 50934256044672, 1825145974743000, 70172455476381440, 2882264153273207360, 125985060813367664640, 5840066736661562391968, 286204501001426735001600

Offset: 0

Carlos Alves, Aug 07 2009

nonn

See A163951 for the cases ending with length 2 cycles and fixed points.

			Any period 3 permutation (or disjoint combinations) is one element to be counted.
For n=3, where there are only 2 cases: f1:{1,2,3}->{2,3,1} and f2:{1,2,3}->{3,1,2} but for n>3 there are other elements (non-permutations) to be counted (for instance, with n=5, we count with f:{1,2,3,4,5}->{2,4,5,3,4}).

Alois P. Heinz, Table of n, a(n) for n = 0..387

Cf. A163951, A163947, A163859.

Column k=3 of A222029.

b:= proc(n, m) option remember; `if`(m>3, 0, `if`(n=0, x^m, add(
      (j-1)!*b(n-j, ilcm(m, j))*binomial(n-1, j-1), j=1..n)))
    end:
a:= n-> coeff(add(b(j, 1)*n^(n-j)*binomial(n-1, j-1), j=0..n), x, 3):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 14 2017

b[n_, m_] := b[n, m] = If[m>3, 0, If[n == 0, x^m, Sum[(j - 1)! b[n - j, LCM[m, j]] Binomial[n - 1, j - 1], {j, 1, n}]]];
a[n_] := If[n==0, 0, Coefficient[Sum[b[j, 1] n^(n-j) Binomial[n-1, j-1], {j, 0, n}], x, 3]];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

a(n) ~ (2*exp(4/3)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 18 2017

a(0), a(8)-a(19) from Alois P. Heinz, Aug 14 2017

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

A368858 Number of perfect cube unlabeled endofunctions from n points to themselves.

Original entry on oeis.org

1, 1, 3, 5, 12, 22, 49, 99

Offset: 0

Keith J. Bauer, Jan 08 2024

The same as A368830 but perfect cubes instead of perfect squares.

Cf. A001372, A163859 (labeled version).

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

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A163860 Number of different 4th-power (quartic) mappings of a finite set of n elements into itself.

Views

Author

Keywords

Comments

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

Extensions

A163952 The number of functions in a finite set for which the sequence of composition powers ends in a length 3 cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A368858 Number of perfect cube unlabeled endofunctions from n points to themselves.

Views

Author

Keywords

Comments

Crossrefs