条件付組合せ - ある文字列は何番目に出るか？

質問

[ABC]の3文字を組み合わせて出来る文字列を順番に並べると、

1. A
2. B
3. AA
4. AB
5. BA
6. BB
7. AAA
...

という風になります。
このとき、「Aの次にはBのみが出る」、「Bの次にはAのみが出る」という規則を適用すると、この順番は

1. A
2. B
3. AB
4. BA
...

という風になります。

このような規則を適用したとき、「ある文字列が何番目に現れるか」を求めるには、どのように考えればよいのでしょうか？
たとえば上記の例でいくと、「ABAB」という文字列が現れるのは一体何番目になるかという問題を、計算で求めるにはどのようにすれば良いのでしょうか。

つまり、
任意の文字を組み合わせて出来る文字列を順番に並べたパターンに対して、「ある文字の次には特定の文字しか出ない」というような規則をいくつか適用したとき、ある文字列が何番目に該当するかを求めるにはどうすれば良いか、
という問題です。

曖昧な部分がありましたら申し訳ありません。
補足させて頂きます。
ご回答よろしくお願い致します。

回答No.1

hirono320

＞まずＡＢＣを並べる例でＣが出てこないのはおかしいです。

＞また、どのような規則で制限するかによって、並び方は違ってくるので決まった定式化は難しいと思います。

ただ、文字数の少ない方から辞書順などで番号をつけていくのであれば、２文字(ａ，ｂ)だとａ＝０，ｂ＝１と考えれば２進法の文字列での表現になります。　※ｎ文字なら当然ｎ進法です。

ａ　０
ｂ　１
ａａ　００＝０
ａｂ　０１＝１・・・となります。
０，１，０，１，１０，１１となります。　

ここにａの次はｂがくる、ｂの次にはａがくるという規則で制限すると

ａ　０
ｂ　１
ａｂ　０１＝１
ｂａ　１０
ａｂａ　０１０＝１０　とならびます。

ヒントになりましたでしょうか？

お礼

すっかり間違ってしまいました・・・。
ABCではなく、ABを使った例の間違いでした。
申し訳ありません。

定式化は難しいのですか。ありがとうございます。
辞書順で少し思い出しました。
重複を許した順列・・・で合っていますでしょうか。

01で考えると、
1. a = 0
2. b = 1
3. aa = 00
4. ab = 01
5. ba = 10
6. bb = 11
7. aaa = 000
...
規則をあてると
1. a = 0
2. b = 1
3. ab = 01 = 1
4. ba = 10
5. aba = 010 = 10
6. bab = 101
7. abab = 0101 = 101
8. baba = 1010
...
すみません、もう少し考えてみます。
ご回答ありがとうございました。

補足

なんとか解けました。
ご回答有り難うございます。