The number of permutations with a distance condition

Question

How can I think about this question:

I have a string of As and Bs and I want the number of permutations such that the distance between two Bs is at least 2

for n = 3, the number of valid strings is 4
BAA
AAB
ABA
AAA

for n = 6,
AABAAB is valid 
BABAAA is not valid because the distance between the first two Bs is 1
AAAAAA is valid
BAAAAA is valid
ABAAAB is valid

In your first example (with $n=3$), I think you meant to say the number of valid permutations is $4$, not $3$. (Incidentally, "permutation" is really not the right word here. Just "string," or "word," would be better.) — Barry Cipra, Aug 08 '14 at 02:40

score 2 · Accepted Answer · answered Aug 08 '14 at 02:47

2

Hint: Each acceptable string of length $n\ge3$ either begins with an A followed by an acceptable string of length $n-1$, or with a BAA followed by an acceptable string of length $n-3$.

answered Aug 08 '14 at 02:47

Barry Cipra

79,832

score 1 · Answer 2 · answered Aug 08 '14 at 02:42

Hint: let $C(n)$ be the number of acceptable strings of length $n$ that end with $B$ Let $D(n)$ be the number that end with $BA$ Let $E(n)$ be the number that end with $AA$. Can you write coupled recurrences for each of these? The answer you want is then $C(n)+D(n)+E(n)$ You might start with a spreadsheet to see what is happening. It is OEIS A164316

score 0 · Answer 3 · edited Jun 12 '20 at 10:38

0

This might helps:

Change $B$ to $ABA$, and calculate with dividing cases by the number of $ABA$.

You might also have to consider the case when $B$ is in the end of the sequence.

edited Jun 12 '20 at 10:38

Community

1

answered Aug 08 '14 at 02:38

Jaehyeon Seo

1,873

The number of permutations with a distance condition

3 Answers3