A247026 -id:A247026 - cp's OEIS frontend

A102687 Number of different squares of labeled mappings of a finite set of n elements into itself.

1, 1, 3, 12, 100, 1075, 13356, 197764, 3403576, 66159405, 1438338070

Offset: 0

Eric Wegrzynowski (Eric.Wegrzynowski(AT)lifl.fr), Feb 03 2005

Let A be a finite set of cardinal n, F be the set of mappings from A to A and F_2 be the subset of F including all g such that there exists f in F with g = fof (composition of f with itself). Then a(n) = #F_2.

Cf. A102709.

Column k=2 of A247026.

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;
a[n_] := a[n] = A[n, 2];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 7}] (* Jean-François Alcover, May 27 2019 *)

a(7) from Vladeta Jovovic, Feb 05 2005
a(8) and a(9) from Joshua Zucker, May 18 2006
a(0) from Alois P. Heinz, Sep 09 2014
a(10) from Bert Dobbelaere, Jan 24 2019

A247005 Number A(n,k) of permutations on [n] that are the k-th power of a permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 1, 1, 2, 3, 24, 1, 1, 1, 1, 4, 12, 120, 1, 1, 1, 2, 3, 16, 60, 720, 1, 1, 1, 1, 6, 9, 80, 270, 5040, 1, 1, 1, 2, 1, 24, 45, 400, 1890, 40320, 1, 1, 1, 1, 6, 4, 96, 225, 2800, 14280, 362880, 1, 1, 1, 2, 3, 24, 40, 576, 1575, 22400, 128520, 3628800, 1

Offset: 0

Alois P. Heinz, Sep 09 2014

Number of permutations p on [n] such that a permutation q on [n] exists with p=q^k.

			A(3,0) = 1: (1,2,3).
A(3,1) = 6: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
A(3,2) = 3: (1,2,3), (2,3,1), (3,1,2).
A(3,3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1).
Square array A(n,k) begins:
  1,    1,    1,    1,    1,    1,    1,    1,    1, ...
  1,    1,    1,    1,    1,    1,    1,    1,    1, ...
  1,    2,    1,    2,    1,    2,    1,    2,    1, ...
  1,    6,    3,    4,    3,    6,    1,    6,    3, ...
  1,   24,   12,   16,    9,   24,    4,   24,    9, ...
  1,  120,   60,   80,   45,   96,   40,  120,   45, ...
  1,  720,  270,  400,  225,  576,  190,  720,  225, ...
  1, 5040, 1890, 2800, 1575, 4032, 1330, 4320, 1575, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
William Y. C. Chen and Elena L. Wang, r-Enriched Permutations and an Inequality of Bóna-McLennan-White, arXiv:2502.04136 [math.CO], 2025. See pp. 3, 14.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2.

Columns k=0-10 give: A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008.
Main diagonal gives A247009.
Cf. A247026 (the same for endofunctions), A155510.

with(combinat): with(numtheory): with(padic):
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      `if`(irem(j, mul(p^ordp(k, p), p=factorset(i)))=0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k), 0), j=0..n/i)))
    end:
A:= (n, k)-> `if`(k=0, 1, b(n$2, k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

multinomial[n_, k_List] := n!/Times @@ (k!); b[, 1, ] = 1; b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[If[Mod[j, Product[ p^IntegerExponent[k, p], {p, FactorInteger[i][[All, 1]]}]] == 0, (i - 1)!^j*multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k], 0], {j, 0, n/i}]]]; A[n_, k_] := If[k == 0, 1, b[n, n, k]]; Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 14 2017, after Alois P. Heinz *)

A163859 Number of different cubes of mappings of a finite set of n elements into itself.

Original entry on oeis.org

1, 1, 4, 19, 116, 985, 11026, 145621, 2199240, 37942785, 743755750

Offset: 0

Carlos Alves, Aug 05 2009

The same as A102687, but now for cubic compositions, a(n) is the number of different mappings g that admit at least one mapping f as the cubic root (g=fofof) in terms of the composition.

Column k=3 of A247026.

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

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

A102709 Let a(n,m) = card{f^(n) : f is a mapping from a set of m elements into itself}, where f^(l)(x) = f^(l-1)(f(x)),l>0, f^(0)(x) = x; sequence gives a(n,5).

Original entry on oeis.org

1, 3125, 1075, 985, 580, 1281, 295, 1305, 580, 925, 631, 1305, 220, 1305, 655, 901, 580, 1305, 295, 1305, 556, 925, 655, 1305, 220, 1281, 655, 925, 580, 1305, 271, 1305, 580, 925, 655, 1281, 220, 1305, 655, 925, 556, 1305, 295, 1305, 580, 901, 655, 1305, 220

Offset: 0

Vladeta Jovovic, Feb 05 2005

nonn

Sequence appears to have a rational o.g.f. - Ralf Stephan, May 18 2007

Ray Chandler, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (-1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 1).

Cf. A102687.

Row n=5 of A247026.

Join[{1, 3125, 1075, 985},LinearRecurrence[{-1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 1},{580, 1281, 295, 1305, 580, 925, 631, 1305, 220, 1305, 655, 901},45]] (* Ray Chandler, Sep 08 2015 *)

Empirical g.f.: 1+x*(60*x^14 +480*x^13 +2360*x^12 +2584*x^11 +3099*x^10 +2188*x^9 -522*x^8 -4057*x^7 -8367*x^6 -9981*x^5 -12231*x^4 -9965*x^3 -8310*x^2 -4200*x -3125) / ((x -1)*(x +1)*(x^2 -x +1)*(x^2 +1)*(x^2 +x +1)*(x^4 +x^3 +x^2 +x +1)). - Colin Barker, Aug 07 2013

a(0) inserted by Alois P. Heinz, Sep 10 2014

A103950 a(n) is the number of distinct n-th powers of functions {1, 2, 3, 4, 5, 6} -> {1, 2, 3, 4, 5, 6}.

Original entry on oeis.org

1, 46656, 13356, 11026, 5721, 12942, 3136, 13806, 5601, 9286, 5952, 13806, 1921, 13806, 6816, 8422, 5601, 13806, 3136, 13806, 4737, 9286, 6816, 13806, 1921, 12942, 6816, 9286, 5601, 13806, 2272, 13806, 5601, 9286, 6816, 12942, 1921, 13806, 6816

Offset: 0

David Wasserman, Feb 23 2005

For n > 4, a(n+60) = a(n).

Ray Chandler, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (-1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 1).

Cf. A102687, A102709, A103947-A103949.

Row n=6 of A247026.

Join[{1, 46656, 13356, 11026, 5721},LinearRecurrence[{-1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 1},{12942, 3136, 13806, 5601, 9286, 5952, 13806, 1921, 13806, 6816, 8422, 5601},34]] (* Ray Chandler, Sep 08 2015 *)

G.f.: (120*x^16 +1860*x^15 +8520*x^14 +43110*x^13 +48594*x^12 +67518*x^11 +57786*x^10 +26294*x^9 -27373*x^8 -89675*x^7 -122940*x^6 -160740*x^5 -136773*x^4 -117696*x^3 -60014*x^2 -46657*x -1) / ((x -1)*(x +1)*(x^2 -x +1)*(x^2 +1)*(x^2 +x +1)*(x^4 +x^3 +x^2 +x +1)). - Colin Barker, Aug 07 2013

A103947 a(n) is the number of distinct n-th powers of functions {1, 2} -> {1, 2}.

Original entry on oeis.org

1, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3

Offset: 0

David Wasserman, Feb 21 2005

			a(4) = 3: the four functions {1, 2} -> {1, 2} are f(x) = 1, g(x) = 2, h(x) = x and j(x) = 3 - x. f^4(x) = f(f(f(f(x)))) = 1; so f^4 = f. Similarly, g^4 = g, h^4 = h and j^4 = h, so there are 3 distinct 4th powers.

Index entries for linear recurrences with constant coefficients, signature (0,1).

Cf. A102687, A102709, A103948, A103949, A103950.
Cf. A158515.
Row n=2 of A247026.

Join[{1},LinearRecurrence[{0, 1},{4, 3},104]] (* Ray Chandler, Sep 08 2015 *)

For n > 2, a(n) = a(n-2).
G.f.: (1+4*x+2*x^2)/(1-x^2). - Jaume Oliver Lafont, Mar 20 2009
a(n) = (n mod 2)+(2 mod (n+2))+1. - Aaron J Grech, Sep 02 2024
E.g.f.: 3*cosh(x) + 4*sinh(x) - 2. - Stefano Spezia, Sep 04 2024

A103949 a(n) is the number of distinct n-th powers of functions {1, 2, 3, 4} -> {1, 2, 3, 4}.

Original entry on oeis.org

1, 256, 100, 116, 73, 148, 44, 148, 73, 116, 76, 148, 41, 148, 76, 116, 73, 148, 44, 148, 73, 116, 76, 148, 41, 148, 76, 116, 73, 148, 44, 148, 73, 116, 76, 148, 41, 148, 76, 116, 73, 148, 44, 148, 73, 116, 76, 148, 41, 148, 76, 116, 73, 148, 44, 148, 73, 116, 76, 148

Offset: 0

David Wasserman, Feb 21 2005

For n > 2, a(n) = a(n+12).

Index entries for linear recurrences with constant coefficients, signature (-1, -1, 0, 1, 1, 1).

Cf. A102687, A102709, A103947, A103948, A103950.

Row n=4 of A247026.

LinearRecurrence[{-1,-1,0,1,1,1},{1,256,100,116,73,148,44,148,73},60] (* Harvey P. Dale, Jun 22 2015 *)

G.f.: (24*x^8+132*x^7+92*x^6-80*x^5-288*x^4-472*x^3-357*x^2-257*x-1) / ((x-1)*(x+1)*(x^2+1)*(x^2+x+1)). - Colin Barker, Aug 07 2013

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

A103948 a(n) is the number of distinct n-th powers of functions {1, 2, 3} -> {1, 2, 3}.

Original entry on oeis.org

1, 27, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19, 12, 21, 10, 21, 12, 19

Offset: 0

David Wasserman, Feb 21 2005

Index entries for linear recurrences with constant coefficients, signature (-1, 0, 1, 1).

Cf. A102687, A102709, A103947, A103949, A103950.

Row n=3 of A247026.

Join[{1, 27},LinearRecurrence[{-1, 0, 1, 1},{12, 19, 12, 21},68]] (* Ray Chandler, Sep 08 2015 *)

For n > 1, a(n) = a(n+6).

G.f.: (6*x^5-3*x^4-30*x^3-39*x^2-28*x-1) / ((x-1)*(x+1)*(x^2+x+1)). - Colin Barker, Aug 07 2013

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

cp's OEIS Frontend

A102687 Number of different squares of labeled mappings of a finite set of n elements into itself.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A247005 Number A(n,k) of permutations on [n] that are the k-th power of a permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A163859 Number of different cubes of mappings of a finite set of n elements into itself.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A102709 Let a(n,m) = card{f^(n) : f is a mapping from a set of m elements into itself}, where f^(l)(x) = f^(l-1)(f(x)),l>0, f^(0)(x) = x; sequence gives a(n,5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A103950 a(n) is the number of distinct n-th powers of functions {1, 2, 3, 4, 5, 6} -> {1, 2, 3, 4, 5, 6}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A103947 a(n) is the number of distinct n-th powers of functions {1, 2} -> {1, 2}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A103949 a(n) is the number of distinct n-th powers of functions {1, 2, 3, 4} -> {1, 2, 3, 4}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Crossrefs

Extensions

A103948 a(n) is the number of distinct n-th powers of functions {1, 2, 3} -> {1, 2, 3}.

Views

Author

Keywords