A373768 Number of permutations of {1...n} P such that P <= R, lexicographically, for all R that is a root of P (i.e., R^k = P for some k).

1, 1, 2, 5, 15, 57, 308, 1731, 12276, 97646, 884948, 8069602, 90805706

Offset

0,3

Comments

All permutations that satisfy this property can be found using an algorithm that is akin to the sieve of Eratosthenes.

Links

Table of n, a(n) for n=0..12.

Example

a(3) = 5; the sole permutation not counted is P = (3,1,2) since it fails to have P <= R at root R = (2,3,1) (that R being P = R^2 in this case).

Prog

(Python)
from itertools import permutations
def a(n):
    perms = permutations(range(n))
    not_term = set()
    i = 0
    for p in perms:
        if p not in not_term:
            P = tuple(p[i] for i in p)
            while P != p:
                not_term.add(P)
                P = tuple(p[i] for i in P)
            i += 1
    return i

Crossrefs

Sequence in context: A351158 A187981 A334155 * A348365 A048192 A078792

Adjacent sequences: A373765 A373766 A373767 * A373769 A373770 A373771

Keyword

nonn,hard,more

Author

Bryle Morga, Jun 18 2024

Extensions

a(12) from Michael S. Branicky, Jun 18 2024

Status

approved