方針
(1) は9マスの独立集合を個数別に数える。(2) は3個以上の同一文字の連続があるときだけ短くなる。連続長が1で終わる列と2で終わる列に分け,補集合を漸化式で数える。
解答
(1) 黒マス1個は9通り,2個は隣接しない組を数えて16通り,3個は8通り,4個は中央を除く4隅の1通りである。合計は 通り。
(2) 連続長が3以上の部分があるときに限り短くなる。連続長が1で終わる適格列数を ,2で終わるものを とすると,,初期値は である。これより適格列総数は でそれぞれ 。したがって求める確率は である。