Anand Jain - cp's OEIS frontend

A383459 Minimum number of cycles in any permutation in S_n of the highest order (A000793(n)).

1, 1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 4, 3, 3, 3, 4, 3, 4, 5, 5, 4, 4, 5, 4

Offset: 1

Anand Jain, Mar 22 2025

Landau's function g(n) = A000793(n) gives the maximum order of any permutation on n elements.

The number of permutations of order g(n) is A074059, and the number of different cycle types of permutations of order g(n) is A074064. a(n) is the maximum number of cycles in any permutation of order g(n), and A383459(n) is the minimum number of cycles in any permutation of order g(n).

			There are two different cycle types of permutations in S_6 of the maximum order g(6) = 6, for example (123456) and (12)(345)(6). The minimum number of cycles is a(6) = 1 and maximum number is A383458(6) = 3.

Cf. A000793, A074059, A074064, A383458.

A383458 Maximum number of cycles in any permutation in S_n of the highest order (A000793(n)).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 2, 2, 3, 4, 3, 4, 3, 3, 3, 4, 5, 4, 5, 6, 7, 4, 5, 4

Offset: 1

Anand Jain, Mar 22 2025

Landau's function g(n) = A000793(n) gives the maximum order of any permutation on n elements.

The number of permutations of order g(n) is A074059, and the number of different cycle types of permutations of order g(n) is A074064. a(n) is the maximum number of cycles in any permutation of order g(n), and A383459(n) is the minimum number of cycles in any permutation of order g(n).

			There are two different cycle types of permutations in S_6 of the maximum order g(6) = 6, for example (123456) and (12)(345)(6). The minimum number of cycles is A383459(6) = 1 and maximum number is a(6) = 3.

Cf. A000793, A074059, A074064, A383459.

using Combinatorics
arrs = []
for n in 1:25
    ps = integer_partitions(n)
    lcms = lcm.(ps)
    the_max, imax, = findmax(lcms)
    max_order_cyc_idxs = []
    for (i, l) in enumerate(lcms)
        if the_max == l
            push!(max_order_cyc_idxs, i)
        end
    end
    push!(arrs, ps[max_order_cyc_idxs])
end
map(x->maximum(length.(x)), arrs)

A382359 Number of labeled deterministic finite automata with n states and two letters.

Original entry on oeis.org

2, 128, 17496, 4194304, 1562500000, 835884417024, 607687873272704, 576460752303423488, 691636079448571949568, 1024000000000000000000000, 1833841138186726138360895488, 3907429033741066770846918377472, 9769232732262334599652925506494464

Offset: 1

Anand Jain, Mar 22 2025

The first term in the product represents the n-choices for the starting state. The second term represents the subset of states to designate as accepting. The third term is the number of transition functions with an alphabet of length two.

			For n = 1, we have two choices (a(1)=2), either the node is an accept state or not. We have no choice but to send both letters of the alphabet to itself, and only one choice for the start state. Therefore 1*2*1 = 2.
For n = 2, we have 2 choices for starting, 4 choices for which states are accepting, and 2^4 choices for transition functions. So a(2) = 2*4*16 = 128.

Cf. A036289, A062206, A155957.

a[n_]:= n * 2^n * n^(2*n); Array[a,13] (* Stefano Spezia, Sep 03 2025 *)

a(n) = n * 2^n * n^(2*n).
a(n) = n * A155957(n).
a(n) = A036289(n) * A062206(n).

cp's OEIS Frontend

User: Anand Jain

A383459 Minimum number of cycles in any permutation in S_n of the highest order (A000793(n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

A383458 Maximum number of cycles in any permutation in S_n of the highest order (A000793(n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia

A382359 Number of labeled deterministic finite automata with n states and two letters.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula