Bounds on the size of the smallest NFA for L_k-distinct Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:

$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

This language is finite and therefore regular.  Specifically, if $\left|\Sigma\right|=n$, then $\left|L_{k-distinct}\right| = \binom{n}{k} k!$.

What is the smallest non-deterministic finite automaton that accepts this language?

I currently have the following loose upper and lower bounds:


The smallest NFA I can construct has $4^{k(1+o(1))}\cdot polylog(n)$ states.
The following lemma implies a lower bound of $2^k$ states: 



  Let $L ⊆ Σ^*$ be a regular language.  Suppose there are $n$ pairs $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ such that $x_i\cdot w_j \in L$ if and only if $i=j$.  Then any NFA accepting L has at least n states.



Another (trivial) lower bound is $log$$n\choose k$, which is the log of the size of the smallest DFA for the language.


I am also interested in NFAs that accept only a fixed fraction ($0&lt;\epsilon&lt;1$) of $L_{k-distinct}$, if the size of the automaton is smaller than $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$.



Edit: I've just started a bounty that had a mistake in the text.

I meant we may assume $k=polylog(n)$ while I wrote $k=O(log(n))$.

Edit2:

The bounty is going to end soon, so if anyone is interested in what is perhaps an easier way to earn it, consider the following language:

$L_{(r,k)-distinct} :=\{w : w$ contains $k$ distinct symbols and no symbol appear more than $r$ times$\}$.

(i.e. $L_{(1,k)-distinct} = L_{k-distinct}$).

A similar construction as the one in the comments gives $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ sized automaton for $L_{(r,k)-distinct}$.

Can this be improved? What's the best lower bound we can show for this language?
This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $S_A$ and the states from which an accepting state can be reached after reading the elements of $B$ (in any order) by $T_B$. We need that $S_A\cap T_B\ne \emptyset$ if and only if $A\cap B=\emptyset$. This already gives a lower bound for the required number of states and I think it could give something non-trivial.

This problem essentially asks for a lower bound on the number of the vertices of a hypergraph whose line graph is (partially) known. Similar problems were studied e.g., by Bollobas and there are several known proof methods that can be useful.

Update 2014.03.24: In fact if the above hypergraph can be realized on $s$ vertices, then we also get a non-deterministic communication complexity protocol of length $\log s$ for set disjointness with inputs sets of size $a$ and $b$ (in fact the two problems are equivalent). The bottleneck is of course when $a=b=k/2$, for this I could only find the following in Eyal and Noam's book: $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ proved by the standard probabilistic argument. Unfortunately I could not (yet) find good enough lower bounds on this problem but assuming the above is sharp, it would give a lower bound $\Omega(2^k\log n)$ unifying the two lower bounds you have mentioned.