|
＜Melvy＞ |
|
先頭から r 人目に 1 番の人が並ぶとすると，1 〜 r 人目までは 1 〜 r 番の人 (*).
r+1 〜 n 人目までは，r+1, ..., n 番の人が順に並ぶしかないので， n 人のときの並び方の総数を a(n) とおくと， a(1) = 1, a(n) = 1 + a(1) + … + a(n-1) が成り立つ．これを解くと a(n) = 2^(n-1). (*) の証明: r=1 のとき OK. r>1 のとき，2 番は 1 番より前にいる． そして r>2 のとき，3 番が 2 番より前にいるか，2 番は先頭である． 2 番が先頭のときは，その直後は 3 番しかありえないので， 先頭から 2, 3, ..., r, 1, ... と並ぶ． 3 番が 2 番より前にいるときは，4 番が 3 番より前にいるか，3 番は先頭である…と なるので，以下同様に示せる． という考え方をあとで思いつきました (送信時は，先頭の番号で場合分けして足しました)． |
|
12月28日（木） 1:27:34
HomePage:ある大学院生＜Melvy＞の日記 28930 |