Calculate the number of distinct permutations of length n in the closure of a language
The language $S^*$ is regular.  Therefore, it can be expressed by a DFA.  Now use Why isn&#39;t it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038.