Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Welcome to math.SE! If this is a homework question, please tag it as such. Additionally, the community may be more willing to help if you provide some context for the question and show your work up to the point you get stuck - it's easier to teach you how to do the problem than give you the answer. –  Drew Christianson Sep 27 '11 at 21:30
1  
It's not really homework, more like a real life problem, but I recon that it does indeed look like it was ripped off a book. –  Jeanne-Kamikaze Sep 27 '11 at 22:02
    
No worries. Just jumped out as a book problem. –  Drew Christianson Sep 27 '11 at 22:06

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 :/ –  Jeanne-Kamikaze Sep 27 '11 at 21:50
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. –  Ross Millikan Sep 27 '11 at 21:51
    
Well, not two A's in a row should be $2L!L!$. The thing is that I do allow two, but not more. –  Jeanne-Kamikaze Sep 28 '11 at 8:50
    
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. –  Jeanne-Kamikaze Sep 28 '11 at 9:28
    
@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. –  Ross Millikan Sep 28 '11 at 13:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.