Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in \{0,1,2\}^n\mid (\forall k \in \{1,\ldots, n-2\}) (\{b_k, b_{k+1}, b_{k+2}\} \neq \{0, 1, 2\})\,\bigr\}\Bigr|.$$

Hence $a_1 = 3$, $a_2 = 9$, $a_3 = 21$, and so on. One can show that these numbers satisfy the reccurence $$a_{n+1} = 2a_n + a_{n-1}$$ and hence $$a_n = \frac{3}{2}\left((1+\sqrt{2})^n + (1-\sqrt{2})^n\right).$$

Now consider $a_p$ where $p\geq 3$ is a prime. It follows by the binomial theorem that $$a_p \equiv 3 \pmod{p} \tag{*}$$ and a little more work gives that $a_p\equiv 3 \pmod{6p}$.

What I want to know is the following: can we prove the congruence $(*)$ using purely combinatorial methods? In particular, is there a natural way to partition the non-constant ternary strings of length $p$ satisfying the condition into equivalence classes of size $p$ (or sizes which are multiples of $p$ for clear combinatorial reasons)?

The analogous problem where we allow the conditions to "wrap around" (i.e., we allow $k$ to be any positive integer in the definition and set $b_{n+i} = b_i$ for all $i$) is easy: if the length of the string is a prime $p$, the natural action of $C_p$ on the set of such strings (namely, rotation) yields 3 orbits of size $1$ (the constant strings); the other orbits, since $p$ is prime, must have size $p$, so these orbits are our nice equivalence classes.

The same sort of trick doesn't work in this case, since (for instance) the string $01112$ is allowed, but its rotation $11120$ is not. Perhaps something more clever will allow us to get a nice combinatorial proof?

  • $\begingroup$ Probably useless, but what if you treat separately the tuples that cannot be "tamed" by rotations? $\endgroup$ – Matemáticos Chibchas Dec 15 '13 at 20:58
  • $\begingroup$ I would be satisfied with a solution that did this. I considered this some time ago when I was working on this problem but dealing with the non-rotatable strings didn't see to make things much easier. $\endgroup$ – universalset Dec 15 '13 at 21:10
  • $\begingroup$ What you could try to do is the following: Take the three strings of only ones, only twos and only zeros apart (that's your $\equiv 3$) and devide the remaining strings in $p$ groups or a number of groups of size $p$. The obvious way would indeed be something with rotations, but maybe there's some other way. $\endgroup$ – Ragnar Dec 15 '13 at 23:35

I just wanted to suggest another point of view on the problem:

Consider the map $$(\Bbb Z / 3 \Bbb Z)^n \rightarrow (\Bbb Z / 3 \Bbb Z)^{n-1} \\ (b_1,b_2,...,b_n) \mapsto (b_2-b_1,b_3-b_2,...,b_n-b_{n-1}).$$ The map is a 3:1 correspondence, as the pre-image is uniquely determined by fixing a first number. Also, there is a 3:1 correspondence of ternary strings of length p containing an "abc" substring with pairwise distinct a,b,c to ternary strings of length p-1 containing the substring "11" or "22".

Perhaps it is easier to show, that the number of such strings is congruent to 1 mod p (I suspect the zero-string of being the 1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.