3
$\begingroup$

Given two alphabets $A$ and $B$ each of cardinality $L$, how many strings of length $2L$ can I build such that

a) No symbol is repeated and

b) No more than two symbols of A appear consecutively.

1 Answers 1

2

Hints: you are going to use all the letters. First how many orders are there of all the symbols from $A$ alone? How many orders for all the symbols of $B$ alone? These orders can be paired arbitrarily. Then we need to choose which of the $2L$ slots get letters from $A$. How many ways are there to select those? You could give all the odd numbered slots to $A$, or ...

Added: I was thinking no two A's in a row, not no more than two. The number of configurations starts $2,6,16,45,126,357,1016,\ldots $The series appears to be given in OEIS, but I don't see how to derive it. The last entry in comments says this is the series we want. The way I got the numbers was to define $C(n,m)$ as the number of series of $n A$'s and $m B$'s that don't have three or more successive $A$'s and don't end in $A$, $D(n,m)$ as the number of series of $n A$'s and $m B$'s that don't have three or more successive $A$'s and end in one $A$, $E(n,m)$ as the number of series of $n A$'s and $m B$'s that don't have three or more successive $A$'s and end in two $A$'s, $F(n,m)$ as the total number of series don't have three or more successive $A$'s. $C(0,0)=1, D(0,0)=0, E(0,0)=0, C(n,m)=C(n,m-1)+D(n,m-1)+E(n,m-1)$

$ D(n,m)=C(n-1,m), E(n,m)=D(n-1,m), F(n,m)=C(n,m)+d(n,m)+E(n,m)$

I just put it all in a spreadsheet, found the numbers above, and looked up in OEIS.

  • 0
    @Jeanne-Kamikaze: I was thinking no two A's in a row, not no more than two. That makes it much harder, and I now would not think it is a book problem. I have added an update.2011-09-28