# Number of String of Length N

Given a set $S_1$ of m characters and another set $S_2$ of $r$ pairs of characters. Each pairs have different characters and characters in those pairs are essentially from set $S_1$. Make string of length n such that at least one pair from $S_2$ must occur in string and repetition of characters are allowed. Now I have to count number of such strings.

Example: for $m=5, r=3, n=6$.

$S_1={a,b,c,d,e}$ $S_2={(a,c),(b,d),(d,e)}$. Possible strings are $"aaccaa", "aaadeb", "acbdde", "cadbed" "dddbed"$, Following strings are not possible $"aaaaaa", "aabbaa",abeeba$ as these strings does not have both characters from any pairs of $S_2$

• The number doesn't seem like it would depend on just $m,n,r$- it seems like it strongly depends on the specific elements of $S_2$. – Thomas Andrews Oct 7 '13 at 18:55
• @ThomasAndrews, If it depends on element of S2, Can you tell me how to proceed in given specific case. – user99392 Oct 7 '13 at 19:43
• Why is $abdabd$ not allowed, since $(b,d)\in S_2$? I think I might be misunderstanding the question. – Thomas Andrews Oct 7 '13 at 19:45
• @ThomasAndrews You are right I have edited the question. – user99392 Oct 7 '13 at 19:48

Let $A$ be an $m\times m$ matrix with rows and columns labeled by $S_1$ and where the $A_{ij}=0$ if $(i,j)\in S_2$ or $(j,i)\in S_2$ and $A_{ij}=1$ otherwise.

Then the sum of the entries in $A^{k}$ counts the number of words of length $k+1$ which does not contain any consecutive pairs $(i,j)\in S_2$.

So you want to find the sum of the entries of $A^{n-1}$ and then subtract that from $m^n$.

You can find a linear recursion given the characteristic polynomial of $A$.

I don't think there is an easier answer.

Given your example, let $F(n)$ be the number of words of length $n$ that do not contain any of the $S_2$. Then a Wolfram Alpha grind shows me: \begin{align}F(1)&=5\\F(2)&=19\\F(3)&=72\\F(4)&=281\\F(5)&=1083\end{align} and $$F(n+5) = 5F(n+4)-3F(n+3)-7F(n+2)+6F(n+1)$$

The recurrence comes because $x^5-5x^4+3x^3+7x^2-6x$ is the characteristic polynomial for the matrix.

The final count you want is $5^n-F(n)$.