How to count the number of k-ary sequences of length n that use all elements Let $X = \{1, 2, 3\}$, and let $S = \{(a,b,c,d): a,b,c,d \in X, \text{and each element in X appears at least once in a,b,c, or d}\}$. How can I find $|S|$?
In other words, if I have a set $X$, and a set $S$ of 4-ary sequences over $X$, and in each sequence all elements in $X$ appears at least once, how do I count the sequences in $S$? How can I count similar sequences of different lengths?
 A: The existing answers have already shown how to solve your specific example with small numbers. The solution for the general case is a paradigmatic application of the inclusion–exclusion principle.
Let $n$ denote the size of the alphabet ($n=3$ in your case). We want to count the strings of length $k$ that use all $n$ letters. The number of strings that use at most $j$ particular letters is $j^k$. Then by inclusion–exclusion the number of strings that use exactly $n$ particular letters is
$$
\sum_{j=0}^n(-1)^j\binom n{n-j}(n-j)^k=\sum_{j=0}^n(-1)^{n-j}\binom njj^k\;.
$$
In your case, with $n=3$ and $k=4$, we get
$$
\sum_{j=0}^3(-1)^{3-j}\binom3jj^4=3^4-3\cdot2^4+3\cdot1^4-0^4=36\;.
$$
A: If one element appears twice and the other two once we have ${4!\over 2!1!1!}$ arrangements. Now you can choose on 3 ways this element which appears twice, so 
$$ |S| = 3\cdot {4!\over 2!1!1!}  = 36$$
A: Hint: So, $a$, $b$, $c$, and $d$ must be a permutation of $1$, $2$, $3$, and one repeated element $x\in X$.  In how many ways can we choose $x$?  In how many ways can we permute $4$ objects consisting three distinct types of objects, with one type occurring twice and each of the remaining two types occurring once?
