Number of n-words such that a and b are not neighbors.

Question:How many n-words from the alphabet {a,b,c,d} are such that a and b are never neighbors?

1.There are $4^n$ ways to arrange the four letters.

2.There are $(n-1)$$2^{n-1}$ ways of arranging a and b together.(is it so?)

3.Hence,the required number is $4^n$-$(n-1)$$2^{n-1}$.

Have I counted the right number of things?

I am looking for a very beautiful Combinatoric proof.

Edit:I realized I had incorrectly assumed that a and b occurred only once in the sequence.

Solution 1:

I found something with recursion, I don't know if it helps.

Let $s_n$ be the number of $n$-words ending in $a$ (equal to the number of $n$-words ending in $b$) and let $t_n$ be the number of $n$-words ending in $c$ (equal to the number of $n$-words ending in $d$).

Then we have:

$s_{n+1}=s_n+2t_n$ since an $n+1$ word ending in $a$ is obtained by taking a $n$ word ending in $a,c$ or $d$ and adding an $a$ at the end.

$t_{n+1}=2s_n+2t_{n}$ since an $n+1$ $n$-word ending in $c$ is obtained by taking any $n$-word (ending in any of $a,b,c,d$ and adding a $c$ at the end.

Let $f_n$ be then number of $n$-words. Then $f_n=t_{n+1}$ since an $n+1$-word ending in $c$ can be obtained by taking an $n$ word and just attaching a $c$ at the end.

We have the recursion $f_{n+1}=3s_n+3s_n+4t_n+4t_n$ since a $n$-word ending in $a$ can be extended in three ways to an $n+1$-word (likewise for wn $n$-word ending in $b$. On the other hand words ending in $b$ can ended in $4$ ways.

So $f_{n+1}=6s_n+8t_n$, using $s_n+s_n+t_n+t_n=f_n$ we get $f_{n+1}=3f_n+2t_n=3f_n+2f_{n-1}$

So $f_{n+1}=3f_n+2f_{n-1}$.

We could obtain an exponential formula similar to that of the fibonaccis, but I have a gut feeling it will have an irrational coefficient just like the formula for the fibonaccis.

Lets use the recursion to compute some values.

By inspection we have:

$f_1=4,f_2=16-2=14$.

From here:

$f_3=50,f_4=178,f_5=634,f_6=2258,f_7=8042,f_8=28642,f_9=102010,f_{10}=363314$

Solution 2:

Your formula in step 2 is wrong.

For a counterexample, let's begin to count the number of $3$-words that have $a$ and $b$ as neighbors. Your formula says there should be $(3-1)2^{3-1}=8$ of them. But look at these:

aba
abb
abc
abd

baa
bab
bac
bad

aab
cab
dab

bba
cba
dba

These are more than $8$! (The two groups have the first occurrence of $ab$ or $ba$ as the first two letters, and the next two groups have the first occurrence as the last two letters.)