>>4
>>19の要領で，
初期状態が○の状態でマルの個数をn個まで増やしたときの並び方を ａｎ 通り．．．①
初期状態が●の状態でマルの個数をn個まで増やしたときの並び方を ｂｎ 通り．．．②
とする（左右は区別する）と，

ａ（ｎ+1）＝ａｎ＋２ｂｎ＋１
ｂ（ｎ+1）＝ａｎ

より，ａｎ＋ｂｎ＝2＾ｎ－1
よって①と②は重複しない