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?
On
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$$
On
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?
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\;. $$