Problem: Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language
$\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$.
Let $L_n = L \cap \Sigma^n$. Determine $|L_n|$; either a closed form or efficient computation scheme is desired.
Example:
Let $\Sigma = \{a, b\}$. Then, $aabaa, ababa, baaba \in L_5$ but $aaabb, baaab,aabbb \notin L_5$.
Note:
This isn't homework or anything... I am a developer at Oklahoma University and this question came up in a discussion with some fellow developer friends of mine. I have some C# code that uses recursion but I believe it to be far from efficient. I can post it if anybody is interested in looking at it as well.