inclusion-exclusion problem

Question

How many base-k sequences are there of length n which contain all k possible symbols? I am trying to solve it using inclusion-exclusion. However, I am actually struggling with the part of counting the number of sequences while at least a symbol is used. i.e. I am counting this: $$|S_0\bigcup S_1\bigcup S_2...\bigcup S_{k-1}|= \sum_0^{k-1}|S_i|-\sum_0^{k-1}|S_i\bigcap S_j|$$+......+... where $S_i$denote the set of sequences which do not contain the symbol i. ($0 \le i\le k-1$)

Answer 1

Check out the sum notations they use on wikipedia to see how they avoid two sets in the intersection being the same or having multiple times the same intersection in their sum.

Say S is the set of all base k sequences of length n and say the set of all base k sequences of length n that miss symbol i is called $S_i$. What you want to compute is $$|S\setminus \bigcup_{i=0}^{k-1}S_i|=k^n-\sum_{\emptyset\neq J\subset\{0,1,...,k-1\}}(-1)^{|J|-1}|\bigcap_{j\in J}S_j|=\\k^n-(|S_0|+|S_1|+...+|S_{k-1}|\\-|S_0\bigcap S_1|-...-|S_{k-2}\bigcap S_{k-1}|\\+|S_0\bigcap S_1\bigcap S_2|+...+|S_{k-3}\bigcap S_{k-2}\bigcap S_{k-1}|\\-...-...\\...\\+(-1)^{k-1}|S_0\bigcap S_1\bigcap ...\bigcap S_{k-1}|)$$

In the first row of the expanded sum every entry is $(k-1)^n$. In the second row every entry is $(k-2)^n$ and so on. The first row has $\binom{k}{1}$ entries, the second row has $\binom{k}{2}$ entries and so on. So $$|S\setminus \bigcup_{i=0}^{k-1}S_i|=k^n-((k-1)^n\binom{k}{1}-(k-2)^n\binom{k}{2}+...+(-1)^{k-1}(k-k)^n\binom{k}{k})=\sum_{i=0}^k (-1)^i(k-i)^n\binom{k}{i}$$ Not sure about further simplifications.

By the way this is also the number of surjective functions from the n element set [n] to the k element set [k] (your sequence has n elements and you want to map them to k characters in a surjective way).