State complexity of permutation on finite languages over a binary alphabet

The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n2−n+22 states. We show that if the language consists of equal length binary strings the bound can be improved to f(n)=n2+n+13 and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L(A) needs f(n) states.