Permutation with inclusion and exclusion

Question

Disclaimer: I do not have any education on strings/matrices, so I am having trouble finding an answer for this question that does not rely on that precondition. If that is the only way to answer the question, any assistance in explaining the notation, etc. would be appreciated.

Problem: In genetics, there are four nucleotides in RNA. A combination of three nucleotides is called a codon, and there are 64 ($4^3$) codons possible. These 64 codons are paired with amino acids to construct the codon table. There are 20 amino acids and 1 STOP value, each of which can be assigned to any given codon. The only requirement for a "viable" codon table is that each of the 21 values must be assigned to at least one codon, but beyond that any level of repetition is allowed. There would be $21^{64}$ total arrangements, but how do I calculate the nonviable arrangements which do not include each value at least once?

Answer 1

Start by including all $21^{64}$ genetic codes (codon tables). Then inclusion/exclusion starts:

• Exclude those codes that code for only 20 meanings. There are $\binom{21}{20}$ ways to choose those meanings, then $20^{64}$ ways to assign the meanings we picked to the codons.
• Include the codes with 19 meanings: $+\binom{21}{19}×19^{64}$.
• Exclude the codes with 18 meanings: $-\binom{21}{18}×18^{64}$, etc.

This continues until we get to the codes with only one meaning. Therefore our final count works out to be $$N=\sum_{j=1}^{21}(-1)^{21-j}\binom{21}jj^{64}\approx1.51×10^{84}$$

In a generalised setting, with $k$ meanings and $n$ codons, the number of viable codes is $$N=k!\left\{n\atop k\right\}=\sum_{j=1}^k(-1)^{k-j}\binom kjj^n$$ where $\left\{n\atop k\right\}$ is the Stirling number of the second kind, the number of ways to partition $n$ distinct objects into $k$ non-empty subsets.