nを2以上の整数とする。 何も記入されていない白紙がn枚横一列に並んでいる。 これらn枚の白紙に、左から順に0か1を次の条件(*)を満たすように記入するとき、その記入の仕方の総数をAnとする。 Anを求めなさい。
(*) 1を連続して記入する場合、必ず1と記入された紙が偶数枚連続しなければならない。
例えば、n=4のとき、【1011】のように記入するならば、1を3回記入することはできる。 1を奇数回記入してはならないということではない点に留意しなさい。
解説をお願いします。
|
No.90075 - 2025/03/28(Fri) 18:42:26
| ☆ Re: 場合の数 / らすかる | | | 末尾が0で終わっているものをB[n] 末尾が01で終わっているものをC[n] 末尾が2個以上の偶数個の1で終わっているものをD[n] 末尾が3個以上の奇数個の1で終わっているものをE[n] とすると A[n]=B[n]+C[n]+D[n]であり B[2]=2 (00と10) C[2]=1 (01) D[2]=1 (11) E[2]=0 (なし) B[n+1]=B[n]+C[n]+D[n] C[n+1]=B[n] D[n+1]=C[n]+E[n] E[n+1]=D[n] となります。 これからA[n]の漸化式を作ると A[2]=4, A[3]=7, A[4]=14, A[5]=26, A[n+4]=A[n+3]+2A[n+2]-A[n] となるのですが、これは多分綺麗な形の一般式では書けません(https://oeis.org/A052535)。 私の解釈に間違いがなければ、問題が正しくない気がします。
ちなみにこの漸化式からA[n]を順次求めると 4,7,14,26,50,95,181,345,657,1252,… のようになり、小さい方いくつかを個別に計算してみると n=2: 2^2=4通り n=3: 2^3通りのうち111だけ不適なので2^3-1=7通り n=4: 2^4通りのうち0111と1110の2つが不適なので2^4-2=14通り n=5: 2^5通りのうち00111,10111,01110,11100,11101,11111の6つが不適なので2^5-6=26通り n=6: 2^6通りのうち 000111,010111,100111,110111, 001110,101110, 011100,011101, 111000,111001,111010,111011, 011111,111110 の14個が不適なので2^6-14=50通り n=7: 2^7通りのうち 0000111,0010111,0100111,0110111,1000111,1010111,1100111,1110111, 0001110,0101110,1001110,1101110, 0011100,0011101,1011100,1011101, 0111000,0111001,0111010,0111011, 1110000,1110001,1110010,1110011,1110100,1110101,1110110, 0011111,1011111, 0111110, 1111100,1111101, 1111111 の33個が不適なので2^7-33=95通り のようになって(私の解釈が正しければですが)正しそうです。
|
No.90079 - 2025/03/29(Sat) 08:45:11 |
|