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

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

Offset: 1

Author

Anand Jain, Mar 22 2025

Keywords

• nonn
• changed

Comments

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.

Examples

			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.
		

Crossrefs

Cf. A036289, A062206, A155957.

Programs

Mathematica

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

Formula

a(n) = n * 2^n * n^(2*n).

a(n) = n * A155957(n).

a(n) = A036289(n) * A062206(n).