Permutations of Project

Consider the alphabet $A$ made out of the letters of the word “$\text{project}$”: $A=\{\text c,\text e,\text j,\text o,\text p,\text r,\text t\}$.
Let $T(n)$ be the number of strings of length $n$ consisting of letters from $A$ that do not have a substring that is one of the $5040$ permutations of “$\text{project}$”.

$T(7)=7^7-7!=818503$.

Find $T(10^{12})$. Give the last $9$ digits of your answer.

This problem explores the concept of exclusion-inclusion. It involves counting total possibilities and then excluding those that violate a certain condition.

1. The total number of strings of length $n$ from the alphabet A is $7^n$.

So, the total number of strings of length $10^{12}$ is $7^{10^{12}}$. We will compute this modulo $10^9$ due to the problem’s request for only the last 9 digits. (As a side note, because $10^9$ is relatively small, it doesn’t overly inflate the calculations.)

2. Now we need to exclude strings that contain permutations of “project” as a substring.

For any given permutation of “project”, the number of strings of length $10^{12}$ that include this permutation is $(10^{12} – 7 + 1)\times 7^{10^{12} – 7}$.

The multiplication by $(10^{12} – 7 + 1)$ is there because that’s how many “slots” are there to fit the 7-letter string into a string of length $10^{12}$.

There are $5040$ such permutations, so we get $5040\times(10^{12} – 6)\times7^{10^{12} – 7}$.

3. But wait, we have double-counted strings that include two occurrences of a permutation of “project”. Each such string is counted twice in the calculation above. We need to add those back in. Similarly, strings with three, four, etc. occurrences are subtracted too many times and need to be added back in. This is the principle of Inclusion-Exclusion.

Note that we don’t have to worry about overlapping occurrences, like “projectproject”, because all the permutations of “project” are distinct: no permutation of “project” can be a substring of another permutation of “project”.

Therefore, the final answer, modulo $10^9$, is

$7^{10^{12}} – 5040*[7^{10^{12} – 7}*(10^{12} – 6) – 7^{10^{12} – 2*7}*(10^{12} – 2*6) + 7^{10^{12} – 3*7}*(10^{12} – 3*6) – …]$

Note: The actual computation involves a large power of 7 modulo $10^9$, and then a sum involving a factorials and combinations. This computation is typically performed with the help of algorithms such as fast exponentiation for calculating large powers in modular arithmetic, and utilizing the properties of factorials and combinations under modular arithmetic. To get the final answer, one will need to use a computer to perform these calculations, as they are far beyond the practicality of being computed by hand.

More Answers: