Counting the number of strings with at least $2$ numbers Let $k$ and $n \ge 3$ be two natural numbers. How many strings in $\{1,...,n\}^k$ contain at least one occurrence of $1$ and $2$, or at least one occurrence of $2$ and $3$ or at least one occurrence of $1$ and $3$?
I tried to break it down and first count the number of strings that contain at least one $1$ which is $n^k - (n-1)^k$ and similarly to at least one $2$ and $3$, but how do we proceed from here?
 A: Use Inclusion/Exclusion.
Let $A$ be the subset of strings containing at least one $1$.
Let $B$ be the subset of strings containing at least one $2$.
Let $C$ be the subset of strings containing at least one $3$.
Then:
$$|(A\cap B)\cup (A\cap C)\cup (B\cap C)| = |A\cap B|+|A\cap C|+|B\cap C| - |(A\cap B)\cap(A\cap C)|-|(A\cap B)\cap (B\cap C)|-|(A\cap C)\cap (B\cap C)|+|(A\cap B)\cap (A\cap C)\cap (B\cap C)| = |A\cap B|+|A\cap C|+|B\cap C|-2|A\cap B\cap C|$$
And continuing to break this down:
$$|A\cup B| = |A|+|B|-|A\cap B|$$
$A\cup B$ is the subset of strings containing at least one $1$ or at least one $2$. So, the complement of that is a string that contains neither a $1$ nor a $2$. Thus:
$$|A\cup B| = n^k-(n-2)^k = 2(n^k-(n-1)^k)-|A\cap B|$$
This gives:
$$|A\cap B| = n^k-2(n-1)^k+(n-2)^k$$
Similarly, we can find the other intersections:
$$|A\cap B| = |A\cap C| = |B\cap C|$$
Next, we need to find $|A\cap B\cap C|$.
We have:
$$|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$
$$n^k-(n-3)^k = 3(n^k-(n-1)^k)-3(n^k-2(n-1)^k+(n-2)^k)+|A\cap B\cap C|$$
which yields:
$$|A\cap B\cap C| = n^k-3(n-1)^k+3(n-2)^k-(n-3)^k$$
Thus, the answer to your original question is:
$$|(A\cap B)\cup (A\cap C)\cup (B\cap C)| = 3(n^k-2(n-1)^k+(n-2)^k)-2(n^k-3(n-1)^k+3(n-2)^k-(n-3)^k) = n^k-3(n-2)^k+2(n-3)^k$$
A: Define sets $A_1,A_2,A_3,A,B,C$ as follows . . .

*

*Let $A_1$ be the set of strings containing  $1$ but not $2$ or $3$.$\\[4pt]$

*Let $A_2$ be the set of strings containing $2$ but not $1$ or $3$.$\\[4pt]$

*Let $A_3$ be the set of strings containing $3$ but not $1$ or $2$.$\\[4pt]$

*Let $A=A_1\cup A_2\cup A_3$.$\\[4pt]$

*Let $B$ be the set of strings containing at least one of $1,2,3$.$\\[4pt]$

*Let $C$ be the set of strings containing at least two of $1,2,3$.

The goal is to find $|C|$.

For $1\le i\le 3$, we have $|A_i|=(n-2)^k-(n-3)^k$.

For $|A|$, since $A_1,A_2,A_3$ are disjoint, we get $|A|=3\bigl((n-2)^k-(n-3)^k\bigr)$.

For $|B|$, we get $|B|=n^k-(n-3)^k$.

For $|C|$, we have $|C|=|B|-|A|$, hence $|C|=n^k-3(n-2)^k+2(n-3)^k$.
A: I cannot resist applying the generalised inclusion exclusion principle:

Given set $A_i$ for $i\in \{1,\dots,n\}$, let $n_k=\sum |A_{i(1)}\cap \dots \cap A_{i(k)}|$, where $\{i(1),\dots,i(k)\}$ ranges over all subsets of $\{1,\dots,n\}$ of size $k$. The regular principle of inclusion exclusion says that
$$
\text{# elements contained in at least $1$ of the $A_i$}=\sum_{k\ge 1}(-1)^{k-1}n_k
$$
More generally,
$$
\text{# elements contained in at least $m$ of the $A_i$}=\sum_{k\ge m}(-1)^{k-m}\binom{k-1}{m-1}n_k\tag1
$$
$$
\text{# elements contained in exactly $m$ of the $A_i$}=\sum_{k\ge m}(-1)^{k-m}\binom{k}{m}n_k\tag2
$$

We will only use $(1)$, but I stated $(2)$ for completeness to show the connection with the linked answer.
In your case, let $A_1$ be the set of strings which do not contain $1$, and similarly for $A_2$ and $A_3$. You want to count the number of strings which occur in at most one of the $A_i$ for $i\in \{1,2,3\}$. This is the complement of the set of strings which occur in at least $2$ of the $A_i$, so we can apply $(1)$. We find  $n_2=3(n-2)^k$ and $n_3=(n-3)^k$, so the number of sets missing at least $2$ symbols is
$$
\binom{2-1}{2-1}n_2-\binom{3-1}{2-1}n_3=3(n-2)^k-2(n-3)^k
$$
To get sets missing at most one symbol, subtract this expression from $n^k$.
