toto（サッカーくじ）の組み合わせ

toto（サッカーくじ）で、同じ数字が３つ以上連続しない
組み合わせは何通りありますか？

No.2 ベストアンサー 回答者： kony0 回答日時： 2004/04/13 23:32

状態１：「直前の２つが異なる」かつ「３つ以上連続したことがない」

状態２：「直前の２つが同じ」かつ「３つ以上連続したことがない」
状態３：「３つ以上連続したことがある」

０，１，２を１つずつ読みこんで、上記の状態を遷移する。（有限オートマトン・言語受理の概念です。）
ｎ文字読みこんだとき（3^n通りの順列がある）状態ｉであるものの総数をN(n,i)とする。

N(1,1)=3, N(1,2)=0, N(1,3)=0

N(n,1) = 2*N(n-1,1) + 2*N(n-1,2)
N(n,2) = N(n-1,1)
N(n,3) = N(n-1,2) + 3*N(n-1,3)

N(1,1)=3, N(2,1)=6
N(n,1) = 2*N(n-1,1) + 2*N(n-2,1)
という３項間漸化式を解けばよい。

「有限オートマトン」はおいといて、大学受験レベルの問題のようですね。

求める答えは N(13,1)+N(13,2)=558,912通り、全通りのうち約35％と思います。（計算は面倒なのでExcelでやりました）

#1さんと答えが違います・・・でも考え方は間違ってないと思うのですが。。。

No.3 回答者： eatern27 回答日時： 2004/04/14 18:53

#1です。

#2さんと答えが違うということなので,再び計算しなおしたら、558912通りになりました。(#2さんと同じ答えです)

どうやら、私の計算が間違っていたみたいです。すいませんでした。

No.1 回答者： eatern27 回答日時： 2004/04/13 20:15

totoって、１３試合を0,1,2の番号で予想するんですよね？

だとすれば、339648通りだと思います。(計算ミスしてるかもしれません)

導く過程は複雑(？)なので、省略します。が、必要なら補足に書いてください。