一个较难想的计数问题

aishuxue

黑, 白球共10个排成一列, 满足对任意连续若干个球, 黑白球数差的绝对值均不超过2, 则满足要求的排列共有多少种？

aishuxue

同色球不加以区分.

isee

联想到个类似的 概率问题，方格黑白染色

aishuxue

方法这么高级？

tommywong

oeis.org/A027383
$a_{2n}=3\times 2^n-2$
$a_{n+2}=2a_n+2$
$a_{10}=3\times 2^5-2=94$

tommywong

設：
$bb_n$為球數差偏1黑球且最後黑球，例如黑、黑白黑、黑白黑白黑
$bw_n$為球數差偏1黑球且最後白球，例如黑黑白、黑白黑黑白、黑黑白黑白
$Bb_n$為球數差偏2黑球且最後黑球，例如黑黑、黑黑白黑
$ww_n$為球數差偏1白球且最後白球
$wb_n$為球數差偏1白球且最後黑球
$Ww_n$為球數差偏2白球且最後白球

$bb_{n+1}=Bb_n+ww_n$
$bw_{n+1}=Ww_n+Bb_n$
$Bb_{n+1}=bw_n$
$ww_{n+1}=Ww_n+bb_n$
$wb_{n+1}=Bb_n+Ww_n$
$Ww_{n+1}=wb_n$

$a_{n+1}=3Bb_n+3Ww_n+ww_n+bb_n+bw_n+wb_n=a_n+2Bb_n+2Ww_n$
$Bb_{n+2}+Ww_{n+2}=bw_{n+1}+wb_{n+1}=2(Bb_n+Ww_n)$
$Bb_2+Ww_2=Bb_3+Ww_3=2$
$\displaystyle Bb_n+Ww_n=2^{[\dfrac{n+1}{2}]}$
$\displaystyle \boxed{a_{n+1}=a_n+2^{[\dfrac{n+1}{2}]}}$
$\displaystyle a_{n+2}=a_n+2^{[\dfrac{n+1}{2}]}+2^{[\dfrac{n+2}{2}]}$
$\displaystyle a_{2n}=a_{2n-2}+3\times 2^{n-1}=4+\sum_{k=2}^n 3\times 2^{k-1}=3\times 2^n-2$
$\displaystyle a_{2n-1}=a_{2n-3}+2^n=2+\sum_{k=2}^n 2^k=2^{n+1}-2$