2022大学入学共通テスト数学ⅠA確率

質問

今回（2022）の大学入学共通テストでは、プレゼント交換会で自分のプレゼントを受け取らない確率を考察させる問題が出題されました。ほぼ同義になるように要約すると、n人が1人1個ずつ異なるプレゼントを用意し、これを一度集めてからでたらめに元のn人に1個ずつ配るとき、誰も自分の用意したプレゼントを受け取らない確率（以下p(n)とする）について、n＝2、3、4、5のときを順に求める問題です。
予備校の解説等を見ると、この確率の分子に当たるものは完全順列などと呼ばれているらしく、さらにwiki等で調べると包除原理等を用いることで
p(n)＝∑_{k＝0～ｎ}（(-1)^k・(1／k!)）
を導くことができることがわかりました。このことは、
p(1)＝0，p(n)＝p(n-1)＋(-1)^n・(1／n!)…（＊）
が成り立つこととほぼ同義ですが、この式に興味を持ちました。漸化式（＊）には直観的な意味があるのでしょうか。p(n)は、nが奇数のときはp(n-1)から1／n!を引けばよく、nが偶数のときはp(n-1)に1／n!を足せばよいということですが、直接説明する方法があるでしょうか。
もし直観的に捉えることができるのであれば、この漸化式に受験生が気づき、超高速で解けた可能性もあるということになります。アイディアがあったら是非ご教示いただきたく存じます。よろしくお願いします。

回答No.7

f272 · ベストアンサー

> 説明文を読まずに見たのでちんぷんかんぷんでした…

元文献でも"Using cycle notation"だけで済ませていますからね。その上にこの文献では巡回置換表現のうちでも，1つの巡回の中では最小の要素が最初に来るようにし，その最小の要素によって昇順に巡回を並べることにしています。こうすれば必ず一意的に表現できます。
ちなみにD[n]：n個の要素を持つ集合{1,2,...,n}の置換のうち不動点がないものの数
D：n個の要素を持つ完全順列の集合
F：n個の要素を持つ置換のうち不動点が1つだけあるものの集合
です。したがって|D|=D[n]で|F|=n*D[n-1]です。

> ただ、1：1対応のさせ方に法則性を見いだせず

法則性があるというわけではなく，全単射(言い換えると上への1対1写像)の規則を人為的に決めただけですよ。
以下の規則でαは不動点です。Fの要素を⇔の左に，Dの要素を⇔の右に書いて対応付けをしています。
Fの最初の巡回が3要素以上のとき
Case I: (1 a1 a2 ... aj)...(α)... ⇔ (1 α a1 a2 ... aj)...
Fの最初の巡回が2要素でa1≠2のとき
Case II: (1 a1)...(α)... ⇔ (1 α a1)...
Fの最初の巡回が1要素で2番目の巡回が2要素のとき
Case III: (1)(2 a1)... ⇔ (1 a1 2)...
Fの最初の巡回が1要素で2番目の巡回が3要素以上のとき
Case IV: (1)(2 a1 a2 ... aj)... ⇔ (1 a1)(2 a2 ... aj)...

Fの最初の巡回が2要素で(1 2)で始まるとき，つまりk≧1に対してσk=(1 2)(3 4)...(2k-1 2k)で始まるときは，さらに場合分けをします。と言っても本質的には上記と同じことです。
Fのσkを除いた最初の巡回が3要素以上のとき
Case I: σk(2k+1 a1 a2 ... aj)...(α)... ⇔ σk(2k+1 α a1 a2 ... aj)...
Fのσkを除いた最初の巡回が2要素でa1≠2のとき
Case II: σk(2k+1 a1)...(α)... ⇔ σk(2k+1 α a1)...
Fのσkを除いた最初の巡回が1要素で2番目の巡回が2要素のとき
Case III: σk(2k+1)(2k+2 a1)... ⇔ σk(2k+1 a1 2k+2)...
Fのσkを除いた最初の巡回が1要素で2番目の巡回が3要素以上のとき
Case IV: σk(2k+1)(2k+2 a1 a2 ... aj)... ⇔ σk(2k+1 a1)(2k+2 a2 ... aj)...
ここまでは，規則で全単射がありますからDとFの数は同じです。

上記規則では対応できていないものは，以下の通りになります。
nが偶数のとき
(1 2)(3 4)...(n-3 n-2)(n-1)(n)のときは，σk(ただしk=n/2-1)で始まりますが，上記規則にはありません。しかしこれはDにもFにも含まれません。
(1 2)(3 4)...(n-3 n-2)(n-1 n)のときのときは，σk(ただしk=n/2)で始まりますが，上記規則にはありません。しかしDには含まれ，Fには含まれません。
nが奇数のとき
(1 2)(3 4)...(n-2 n-1)(n)のときのときは，σk(ただしk=(n-1)/2)で始まりますが，上記規則にはありません。しかしDには含まれず，Fには含まれます。

これで
nが偶数のときには|D|=D[n]=|F|+1=n*D[n-1]+1
nが奇数のときには|D|=D[n]=|F|-1=n*D[n-1]-1
だとわかりました。

お礼

丁寧なご説明、本当にありがとうございます！
全単射の決め方がこんなに複雑なんですね…
#3さんがおっしゃったとおり確かにこれは受験生が気づけるレベルの話ではないですね。
やはり3項間漸化式に気づくのがやっとだと思いました。
でもすごく勉強になりました。ありがとうございました。

回答No.6

f272

#3さんが紹介しているところでは、以下のように説明しています。
分かりやすいように具体的な数で言います。
n=2のときD[2]=1で(1 2)です。この記法で(a b c)とあればa人目の人のプレゼントはb人目の人にわたり、b人目の人のプレゼントはc人目の人にわたり、c人目の人のプレゼントはa人目の人にわたることを意味します。
次はn=3でD[3]=2で(1 2 3)、(1 3 2)ですが、これを次のように考えます。n=2のときの(1 2)をもとにn=3で1人だけは自分のプレゼントを受け取る人がいる状況を考えると3*D[2]通りがあります。つまり(1)(2 3)、(1 3)(2)、(1 2)(3)ですね。
(1)(2 3)⇔(1 3 2) (Case III)
(1 3)(2)⇔(1 2 3) (Case II)
(1 2)(3)⇔?
というようにD[3]の要素と1対1の対応が付きますが、(1 2)(3)は対応が付きません。D[3]=3*D[2]-1
次はn=4です。
(1 3 2)から
(1)(2 4 3)⇔(1 4)(2 3) (Case IV)
(1 4 3)(2)⇔(1 2 4 3) (Case I)
(1 4 2)(3)⇔(1 3 4 2) (Case I)
(1 3 2)(4)⇔(1 4 3 2) (Case I)
(1 2 3)から
(1)(2 3 4)⇔(1 3)(2 4) (Case IV)
(1 3 4)(2)⇔(1 2 3 4) (Case I)
(1 2 4)(3)⇔(1 3 2 4) (Case I)
(1 2 3)(4)⇔(1 4 2 3) (Case I)
というようにD[4]の要素と1対1の対応が付きますが、(1 2)(3 4)だけは対応するものがありません。D[4]=4*D[3]+1
次はn=5です。
(1 4)(2 3)から
(1)(2 5)(3 4)⇔(1 5 2)(3 4) (Case III)
(1 5)(2)(3 4)⇔(1 2 5)(3 4) (Case II)
(1 5)(2 4)(3)⇔(1 3 5)(2 4) (Case II)
(1 5)(2 3)(4)⇔(1 4 5)(2 3) (Case II)
(1 4)(2 3)(5)⇔(1 5 4)(2 3) (Case II)
(1 3)(2 4)から
(1)(2 4)(3 5)⇔(1 4 2)(3 5) (Case III)
(1 4)(2)(3 5)⇔(1 2 4)(3 5) (Case II)
(1 4)(2 5)(3)⇔(1 3 4)(2 5) (Case II)
(1 3)(2 5)(4)⇔(1 4 3)(2 5) (Case II)
(1 3)(2 4)(5)⇔(1 5 3)(2 4) (Case II)
(1 2)(3 4)から
(1)(2 3)(4 5)⇔(1 3 2)(4 5) (Case III)
(1 3)(2)(4 5)⇔(1 2 3)(4 5) (Case II)
(1 2)(3)(4 5)⇔(1 2)(3 5 4) (σ1付きのCase III)
(1 2)(3 5)(4)⇔(1 2)(3 4 5) (σ1付きのCase II)
(1 2)(3 4)(5)⇔?
というようにD[5]の要素と1対1の対応が付きますが、(1 2)(3 4)(5)だけは対応するものがありません。
(1 2 4 3)などから(1 2 4 3)(5)⇔(1 5 2 4 3)(Case I)などは簡単ですので省略します。D[5]=5*D[4]-1
このような1対1の対応付けの方法を具体的に元文献では示しています。一般的にD[n]=n*D[n-1]+(-1)^n

お礼

何度も何度も本当にありがとうございます。そして何度も何度も質問してすみません…

英語の文献の表記の意味が分かりました！
(12)(34)などと書いているのは、ループの組み合わせだったんですね。説明文を読まずに見たのでちんぷんかんぷんでした…

ただ、1：1対応のさせ方に法則性を見いだせず、あと一歩理解に至りませんでした…(caseⅡ)などの表記がヒントなのでしょうか？

回答No.5

f272

> ただ、a(n)が何を表しているかわかりませんでした。

あれ？Wikiで完全順列も見たんですよね。そこに書いてあるモンモール数a[n]です。p[n]=a[n]/n!になります。モンモール数の説明も
n番目に置く数の選び方は 1 から(n - 1)までの(n - 1)通りである。ここで選んだ数を i とする。次に、i番目が n かどうかで場合分けをする。i番目が n であれば、i番目に置かれた n とn番目に置かれた i を除く(n - 2)個の数の並べ方の総数は、(n - 2)個の数による完全順列の数、すなわち a[n-2]に等しい。i番目が n でない場合は、n番目に置かれた i を除く(n - 1)個の数の並べ方の総数は、(n - 1)個の数による完全順列の数、すなわち a[n-1]となる。
と書いてある。

お礼

ご教示頂いた漸化式と同値な漸化式
p(n)＝((n−1)/n)p(n−1)＋(1/n)p(n−2)
も同様に説明できることが確認できました。
この式から漸化式(＊)も導けました。ありがとうございます。
(＊)を直接説明するのはやはり難しいでしょうか？

補足

失礼しました。
wikiでは包除原理での説明だけ見ていました…
改めてご説明いただいてモンモール数も理解できました。ありがとうございました。
確率で直接説明することもできるでしょうか？？

回答No.4

ATZ1229tkt

完全順列は非常に有名で結果も綺麗なので、数学が大好きな生徒
ならp(n)＝∑_{k＝0～ｎ}（(-1)^k・(1／k!)）は知っている可能性は
あります。これはe^xの展開をx^nの項までで切ったものにx=-1
を代入したもので意識的に覚えるほどのものではありません。

しかしこれを知っている生徒がこれを使ったかというと多分それ
はないでしょう。これを使えるのは1回でプレゼント交換が終る
確率だけです。誘導に沿って解いていく方がいいです。
時間が足りなさそうだと思ったときに、ソタとチツテトぐらいに
使うという可能性はありますが5点しかありません。
超高速で解けた可能性はありません。

お礼

ご見解をお寄せくださってありがとうございます。
確かに「超」というのは言い過ぎかもしれません。失礼しました。
ただ、この結果を知っていて先に確率p(2)～p(5)を逐次的に求めてしまうことができれば、その誘導部分も逆算して求められる部分も多く、また、最後の条件付き確率もp(5)／{(1/5)*p(4)＋p(5)}と発想しやすくなると思いました。

回答No.3

tmppassenger

一応ここに直接説明する方法を見つけました。
https://www.fq.math.ca/Papers1/55-5/BenjaminOrnstein.pdf

確かに読めば納得しましたが、これを試験中に思いつくかはまったく別の問題。先ずは読んでみてください。

お礼

ご回答ありがとうございます。
ただ、まことに恥ずかしいのですが英語が苦手で読むことができませんでした…
日本語訳はあるでしょうか？

回答No.2

f272

ちょっと書き間違えた
n! = Σ[k=0 to n] C(n,k) a[k]

回答No.1

f272

普通は
a[n]=(n-1)(a[n-1]+a[n-2])
で説明します。この漸化式を解けばよい。また，これを思いつかなくても，C(n,k)を2項係数として
n! = Σ[k=0 to n] C(n,k) a[n]
なら簡単にわかりますから，これから求めてもよいでしょう。

お礼

ご回答ありがとうございます。
ただ、a(n)が何を表しているかわかりませんでした。
p(n)とは別物と思います。また、直観的意味は言葉で説明することができますでしょうか？