The size of subsequence automaton

Given a set of strings, the subsequence automaton accepts all subsequences of these strings. We derive a lower bound for the maximum number of states of this automaton. We prove that the size of the subsequence automaton for a set of k strings of length n is Ω(nk/(k+1)kk!) for any k⩾1. It solves an open problem because only the case k⩽2 was shown before.