$n$-sequences

A sequence of integers $S = \{s_i\}$ is called an $n$-sequence if it has $n$ elements and each element $s_i$ satisfies $1 \leq s_i \leq n$. Thus there are $n^n$ distinct $n$-sequences in total.
For example, the sequence $S = \{1, 5, 5, 10, 7, 7, 7, 2, 3, 7\}$ is a $10$-sequence.
For any sequence $S$, let $L(S)$ be the length of the longest contiguous subsequence of $S$ with the same value.
For example, for the given sequence $S$ above, $L(S) = 3$, because of the three consecutive $7$’s.
Let $f(n) = \sum L(S)$ for all $n$-sequences S.
For example, $f(3) = 45$, $f(7) = 1403689$ and $f(11) = 481496895121$.
Find $f(7\,500\,000) \bmod 1\,000\,000\,009$.

This is a challenging combinatorics question! In such cases, we often look for some form of pattern or a property that we could use to take advantage of.

After a bit of observation, one might notice that if we prefix any n-sequence by a number, it will be an (n+1)-sequence with the same “L” value, hence we might think about doing some sort of dynamic programming.

Firstly, $f(1) = 1$ because we have one 1-sequence $\{1\}$ and $L(\{1\}) = 1$. Then, let’s say we know the value of $f(k)$ for some $k \geq 1$ and want to compute $f(k+1)$.

If we have a (k+1)-sequence, one possible way to construct it is to pick some k-sequence and prefix it with a (k+1) or postfix it with a (k+1). When we prefix it, in addition to the sum of “L” values that already existed in the k-sequence, we add one more to the score (the prefixed (k+1) itself). This contributes $f(k) + k^k \pmod{1,000,000,009}$ to the sum.

If we postfix a (k+1) into the sequence, and the last number of the original k-sequence was already (k+1), it will extend the length of the longest contiguous subsequence of (k+1)’s by one, so it contributes more than just one to the score. To be more precise, for all k-sequences where the last number is (k+1), we add two instead of one to their “L” values, while for the other k-sequences, we add one to their “L” values.

There are $(k+1)^{k-1}$ sequences of length k where the last number is (k+1) (because for the last number we have 1 choice and for the rest we have (k+1) choices), and $k^k – (k+1)^{k-1}$ sequences where the last number is not (k+1) (by subtracting from the total amount of k-sequences). So this contributes $(2 \cdot (k+1)^{k-1} + k^k – (k+1)^{k-1}) \pmod{1,000,000,009}$ to the sum.

Adding these two, $f(k+1) = 2 \cdot f(k) + 2 \cdot k^k – (k+1)^{k-1} \pmod{1,000,000,009}$.

But each (k+1)-sequence is counted twice by this, once when we prefix a (k+1) and once when we postfix it. So $f(k+1) = f(k) + k^k + (k+1)^{k-1} \pmod{1,000,000,009}$. This is the recursion you should use to compute the required value.

Applied iteratively, this recursive formula allows us to compute each $f(n)$ in a cumulative manner. Using a for-loop structure to iterate from n=2 to n=7,500,000, we can easily find the value of $f(7,500,000)$ modulo 1,000,000,009. Make sure to compute your powers modulo 1,000,000,009 at each step to prevent overflow.

More Answers: