count the number of fixed-length sequences with a specific condition

Question

Let $\{1, \dots, i\}$ be a set of consecutive integers. Suppose we are making a sequence $s$ of length-$n$ that does not contain all integers (or does contain all integers) in the given integer set. Specifically, we define an operation $S$ that counts the number of the integers used in the formation of the sequence $s$: $$ S(s) = |\{i: i = s_j \,\,\,\exists j\}| $$ where $s \in \{1,\dots, i\}^n$. What I'd like to do is to count the number of all sequences $s$ such that $S(s) = k$ for $k=1,\dots, i$; namely, $$ |\{ s : S(s) = k\} |. $$

Would there be a neat way to do this?

The strategy I thought about is first pick $k$ distinct integers then count all the possible ways to position them. Then the rest of the sequence elements can be arbitrary. However, I am not so sure whether this approach makes any duplicate sequences.

Anyhow I don't think this is neat; I kind of believe there would be much a neater solution.

Answer 1

You can do this using inclusion–exclusion. For a string with $k$ particular different integers, we have $k$ conditions that each of the integers appear, $\binom kj$ ways to choose $k-j$ particular conditions to violate and $j^n$ strings that violate these $k-j$ conditions. Thus the number of such strings of length $n$ is

$$ \sum_{j=0}^k(-1)^{k-j}\binom kjj^n\;. $$

There are $\binom ik$ ways to pick the $k$ integers, so

$$ |\{ s : S(s) = k\} | = \binom ik\sum_{j=0}^k(-1)^{k-j}\binom kjj^n\;. $$