0
$\begingroup$

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$

Improve this question
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Oct 7 '13 at 18:55
  • $\begingroup$ @ThomasAndrews, If it depends on element of S2, Can you tell me how to proceed in given specific case. $\endgroup$ – user99392 Oct 7 '13 at 19:43
  • $\begingroup$ Why is $abdabd$ not allowed, since $(b,d)\in S_2$? I think I might be misunderstanding the question. $\endgroup$ – Thomas Andrews Oct 7 '13 at 19:45
  • $\begingroup$ @ThomasAndrews You are right I have edited the question. $\endgroup$ – user99392 Oct 7 '13 at 19:48
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$

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.