A102687 -id:A102687 - 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 *)

A103619 Number of permutations of n elements admitting a cube root.

Original entry on oeis.org

1, 1, 2, 4, 16, 80, 400, 2800, 22400, 181440, 1814400, 19958400, 218803200, 2844441600, 39822182400, 556972416000, 8911558656000, 151496497152000, 2579172973977600, 49004286505574400, 980085730111488000, 19584861165821952000, 430866945648082944000

Offset: 0

Vladeta Jovovic, Feb 11 2005

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..250
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 149, Eq. 4.8.2.

Cf. A003483, A103620, A102687, A215716, A215717, A215718.

Column k=3 of A247005.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 3))<>0, 0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1)), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Sep 08 2014

CoefficientList[Series[(1-x^3)^(1/3)/(1-x) * Product[1/3*E^(1/3*x^(3*m)/m) + 2/3*E^(-1/6*x^(3*m)/m) * Cos[1/6*3^(1/2)*x^(3*m)/m],{m,1,20}],{x,0,20}],x] * Range[0,20]! (* Vaclav Kotesovec, Sep 13 2014 *)

E.g.f.: (1-x^3)^(1/3)/(1-x)*Product(1/3*exp(1/3*x^(3*m)/m)+2/3*exp(-1/6*x^(3*m)/m)*cos(1/6*3^(1/2)*x^(3*m)/m), m = 1 .. infinity).

A103620 Number of permutations of n elements admitting a fourth root.

Original entry on oeis.org

1, 1, 1, 3, 9, 45, 225, 1575, 11130, 100170, 897750, 9875250, 108523800, 1410809400, 18332414100, 274986211500, 4127136413400, 70161319027800, 1192076391706200, 22649451442417800, 430247983427262000, 9035207651972502000

Offset: 0

Vladeta Jovovic, Feb 11 2005

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..250
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 149, Eq. 4.8.2.

Cf. A003483, A103619, A102687, A215716, A215717, A215718.

Column k=4 of A247005.

with(combinat): with(numtheory): with(padic):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      `if`(irem(j, mul(p^ordp(4, p), p=factorset(i)))=0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1), 0), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Sep 09 2014

CoefficientList[Series[((1+x)/(1-x))^(1/2) * Product[1/2*Cos[1/2*x^(2*m)/m] + 1/2*Cosh[1/2*x^(2*m)/m],{m,1,20}],{x,0,20}],x] * Range[0,20]! (* Vaclav Kotesovec, Sep 13 2014 *)

E.g.f.: ((1+x)/(1-x))^(1/2)*Product(1/2*cos(1/2*x^(2*m)/m)+1/2*cosh(1/2*x^(2*m)/m), m = 1 .. infinity).

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

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

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

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

A103619 Number of permutations of n elements admitting a cube root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A103620 Number of permutations of n elements admitting a fourth root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

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