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
    If I am not mistaken, I'd have L! perms for $A$, $L!$ perms for $B$, and $\binom {2L} {L}$ to select slots for A. Now, if I didn't want two consecutive $A$ symbols, I could put the As in the even or odd slots and then fill everything else, in which case I'd have $2L!(L-1)!$ strings, I think. The problem is that I can't seem to find a way to build 2-chunks without counting duplicates, and that's where I'm stuck :/2011-09-27
  • 1
    Without the restriction on no two A's in a row, it would just be $L!L!\binom{2L}{L}=(2L)!$, as you can just combine the two alphabets and put all the letters in any order. To resolve the restriction, maybe count by hand the number of strings of 3 a's and 3 b's that don't have two a's in a row. You may see a pattern.2011-09-27
  • 0
    Well, not two A's in a row should be $2L!L!$. The thing is that I do allow two, but not more.2011-09-28
  • 0
    Now I think I might be able to solve this if I count those strings that have exactly one 2-chunk, two 2-chunks, and so on until the max number of 2-chunks that L would allow, and then add everything together + the result for no two A's in a row.2011-09-28
  • 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