How many $20$-digit Quaternary sequences are there- Combinatorics Probem

Question

How many $20$ digit quaternary (alphabet $\{0,1,2,3\}$) sequences are there where no symbol occurs exactly twice?
I know that this can be solved with a generating function. So far, I have $(1+z+(z^2/2!)+(z^3/3!)+...)^4-(z^2/2!)^4= e^4z-(z^2/2!)^4$
However, I do not know how to proceed from here. Any help would be appreciated.

Answer 1

It should not be $$ (1+z+z^2/2+\dots)^4-(z^2/2)^4\tag{1}\label1 $$ It should instead be $$ \Big((1+z+z^2/2+\dots)-z^2/2\Big)^4\tag{2}\label2 $$ $\eqref1$ only eliminates the situation where all characters occur twice. You need to eliminate sitauations where any character occurs twice.

An easier way to write $\eqref 2$ is $$ (e^{z}-z^2/2)^4 $$ Now, expand that with the binomial theorem. Can you take it from here?

Answer 2

I'd use the principle of inclusion and exclusion. There are $4^{20}$ total possible sequences.

From those, you have to subtract the sequences where any one symbol appears exactly twice. For each of the four symbols there are $190 \cdot 3^{18}$ such sequences, so we have to subtract $760 \cdot 3^{18}$.

But this overcorrects. We have to add back the sequences where any two symbols appear exactly twice. That happens $6 \cdot 190 \cdot 153 \cdot 2^{16}$ times.

We've overcorrected again because we've added back sequences where three symbols occur exactly twice. Now we have to subtract the number of sequences where any three symbols appear exactly twice. That happens $4 \cdot 190 \cdot 153 \cdot 120$ times.

It can't happen that four symbols occur exactly twice so we don't need to worry about that term.

So the answer is $4^{20} - 760 \cdot 3^{18}+ 1140 \cdot 153 \cdot 2^{16} - 760 \cdot 153 \cdot 120 = 816,488,891,656.$