So here's what i've got so far:
Let $a_n$ denote the number of string n length formed from the elements of the set {$x, y, z, t$} that do not contain $ xx ,yy ,zz, tt $
There are 12 possible way of dividing this string:

  • $ xy,xz,xt + a_{n-2}$
  • $ yx,yz,yt + a_{n-2}$
  • $ zx,zy,zt + a_{n-2}$
  • $ tx,tz,tz + a_{n-2}$
    So the recurrence relation i got is:
    $a_n = 12a_{n-2}$ $(n \geq 5)$ with the initial condition is $a_3 = 36$
    Im having trouble verifying this solution.

1 Answer 1


This is not correct. You cannot prepend $xy$ onto a string of length $n-2$ if the string starts with $y$. A better approach is to just extend the string by $1$ because you always have the same number of choices for the extension.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Pedro
    Jun 1, 2021 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .