We can think of the n rolls of the die as generating a "word" of length n over the "alphabet" {1,...,k}. Denote the set of all such words by [k]^n. Then [k]^n consists of precisely k^n words.

For i = 1,...,k, we'll say i is "rare" in a word w if i appears at most once in w. We'll say w is "good" if there's at least one i such that i is rare in w.

For i = 1,...,k, define W_i to be the number of words w in [k]^n such that i is rare in w.

The number of "good" words in [k]^n is

| W_1 \cup W_2 \cup \cdots \cup W_k |

which, by inclusion-exclusion, is equal to

|W_1| + |W_2| + \cdots + |W_k|

- ( |W_1 \cap W_2| + |W_1 \cap W_3| + \cdots + |W_{k-1} \cap W_k| )

+ ( |W_1 \cap W_2 \cap W_3| + |W_1 \cap W_2 \cap W_4| + \cdots + |W_{k-2} \cap W_{k-1} \cap W_k| )

- ... (finite sum, of course).

Now what is |W_i|? The set W_i is the disjoint union of:

--the set of words such that i appears exactly 0 times

--the set of words such that i appears exactly 1 time.

The former contains (k-1)^n words, and the latter contains n*(k-1)^{n-1} words

(first choose the position containing the 1 appearance of i, then fill the other positions with things that aren't i).

What is |W_i \cap W_j|? The set W_i \cap W_j is the disjoint union of:

--the set of words such that i appears 0 times and j appears 0 times

--the set of words such that i appears 0 times and j appears 1 time

--the set of words such that i appears 1 time and j appears 0 times

--the set of words such that i appears 1 time and j appears 1 time.

These four sets respectively contain (k-2)^n words, n*(k-2)^{n-1} words,

n*(k-2)^{n-1} words, and n*(n-1)*{k-2}^{n-2} words.

From the previous two paragraphs, we have (switching to Maple syntax on the right side)

|W_i| = binomial(1,0)*(k-1)^n + binomial(1,1)*(k-1)^(n-1)

|W_i \cap W_j| = binomial(2,0)*(k-2)^n + binomial(2,1)*n*(k-2)^(n-1) + binomial(2,2)*n*(n-1)*(k-2)^(n-2)

This pattern continues.

So the number of good words is

binomial(k,1)*( binomial(1,0)*(k-1)^n + binomial(1,1)*n*(k-1)^(n-1) )

- binomial(k,2)*( binomial(2,0)*(k-2)^n + binomial(2,1)*n*(k-2)^(n-1) + binomial(2,2)*n*(n-1)*(k-2)^(n-2) )

+ ...

or more compactly

binomial(k,1)*sum( binomial(1,j)*(k-1)^(n-j)*product(n-i,i=0..j-1), j = 0..1 )

- binomial(k,2)*sum( binomial(2,j)*(k-2)^(n-j)*product(n-i,i=0..j-1), j = 0..2 )

+ binomial(k,3)*sum( binomial(3,j)*(k-3)^(n-j)*product(n-i,i=0..j-1), j = 0..3 )

- ...

which is where I got my formula from.