1
$\begingroup$

Given n and a letter C,how many possible words of length n can be formed that are with no two consecutive C in the word.

For example,if n=3, C='b',then the word bcb,ccc,aab do not have any consecutive occurrence of 'b'.

But bbc,abb,bbb have consecutive occurrence of 'b'.

We can use only letters 'a' to 'z' to form this sort of word and can consider only lowercase letters.

$\endgroup$
1
  • $\begingroup$ Do you know Inclusion-Exclusion? $\endgroup$ – RE60K Sep 20 '14 at 16:09
0
$\begingroup$

Let $f_{n+2}$ be the number of words of length $n+2$ not containing two consecutive letters $b$

We classify the arrangement into two types, the ones that don't end in $b$ and the ones that do end in $b$.

There are clearly $(26-1)f_{n+1}=25f_{n+1}$ arrangements not ending in $b$.(since there are $25$ choices for the last letter and $f_{n-1}$ options for the rest of the sequence)

The other case is slightly trickier, the number of arrangements ending in $b$ is the same as the number of arrangements with $n-1$ letters that don't end in $b$, but this is $25f_n$.

Therefore we get the recursion $f_{n+2}=25(f_{n+1}+f_n)$. It is clear $f_1=26$ and $f_2=675$

Using generating functions we can find

$f_n=(\frac{1}{2}+\frac{27\sqrt29}{290})(\frac{25+5\sqrt29}{2})^n+(\frac{1}{2}-\frac{27\sqrt29}{290})(\frac{25-5\sqrt29}{2})^n$

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