Discrete mathematics – ternary strings.

Question

Let n be a natural number, n≥3. A ternary string is a sequence of n symbols that has some of the digits 0, 1, 2. In other words, a ternary string is a n-permutation with a repetion of the set {∞⋅0,∞⋅1,∞⋅2}. I wonder how to find the number of ternary strings that have at least one 0, one 1 and one 2.

I know that there is a inclusion-exclusion principle, and for that we need to know at least the number of items in the sets, such as A, B and so on.. That being said simply adding the elements in A and B together will show us the elements in the intersection, however we will need to substract the intersection of A and B in order to obtain the number of elements in the union. My confusion is if there is something different by being a ternary string and also by the domain of the sets that has those ternary strings, the mathematical approach I'm thinking of is something like:

A⋃B = A + B – A ⋂ B

Answer 1

Let $X$ be the set of ternary strings of length $n$ with no additional restriction. Let $A$ be the strings of length $n$ with no zeroes. Let $B$ the strings of length $n$ with no ones, and $C$ with no twos.

You are asked to count $|A^c\cap B^c\cap C^c|$, the number of strings who have at least one zero, at least one one, and at least one two.

This can be rearranged as $|(A\cup B\cup C)^c| = |X|-|A\cup B\cup C|$ which expands via inclusion-exclusion as:

$$|X|-|A|-|B|-|C|+|A\cap B|+|A\cap C|+|B\cap C|-|A\cap B\cap C|$$

Each of these terms should be easy to calculate.

For instance, $|A|$ is the number of ternary strings of length $n$ with no zeroes. Each of the $n$ digits in the string then have two possible options... either a 1 or a 2. There are by rule of product $2^n$ possible such strings in $A$.

Plugging everything in and simplifying gives the following expression then:

$$3^n - 3\cdot 2^n + 3\cdot 1^n - 0^n$$

(Note what happens for $n=0$. There does exist one length zero string, the empty string, but it does not satisfy having at least one of each digit, so the expression above correctly simplifies to zero overall. Remember, $0^0$ in combinatorics is equal to $1$)

---

There is a much faster answer but requires more esoteric tools which are not commonly covered in an introductory course that would ask this.

The answer to this question is quite literally one step away from the problems that Stirling Numbers of the Second Kind are meant to count. The value ${n \brace k}$ counts the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. So, break your $n$ positions in your string into three non-empty sets. Then, choose which of those subsets corresponds to the zeroes, the ones, and the twos respectively. This gives an immediate answer with no need to simplify further of:

$$3!\cdot {n\brace 3}$$