場合の数 漸化式

質問

場合の数　漸化式

nを正の整数とする。1からnまでの整数が書かれたカードが各2枚ずつ計2n枚あり，これらをすべて使い2枚ずつの組を作ったとき，すべての組で次の条件を満たす確率をP[n]とする。
条件：組になったカードに書かれた数a，bについて，|a-b|≦1 が成り立つ。

この問題に対し，条件を満たす組み合わせ数をA[n]とすれば，
P[n]=A[n]/{(2n)!/2^n}
で求めることができると考えました。
(組み合わせの総数について，同じものを含む順列と考え，並べた後2枚おきに区切りを入れれば良いと考えました)

しかし，肝心のA[n]が分からないため解答を見たところ，
A[n+2]=A[n+1]+2A[n]
という漸化式がたてられていました。
この漸化式はどのように立式出来るのでしょうか？どなたか解説お願いします。

回答No.2

rfiosrjf · ベストアンサー

恐らく、その漸化式は考え方の前提が違うと思われます。(違っていたら申し訳ありませんが、解答にはP[n]=A[n]/{(2n)!/2^n}と書かれていないのではないでしょうか?)

具体的にn = 2のときを書き出してみると、実はtksmsyshさんの考え方だと

A B
11 22
12 12
12 21
21 21
21 12
22 11
…… #1

の6通り(1, 1, 2, 2の4つを並べて1, 2がそれぞれ2通り重複しているからそれを割っている。)ですよね。

これらのペアをいまA, Bと名付けましたが、その中でもAとBが同じ――即ちA11 B22とA22 B11などが存在しています。これは
コインでもお馴染みの、
「2枚の裏表の分かるコインを投げたときに、1枚が表、もう1枚が裏である確率を求めよ」
という問題に似ています。

表 - 表
表 - 裏
裏 - 表
裏 - 裏

の2^2通りが同様に確からしいと考えるのが妥当で、求める確率は2/4です。(決して1/3ではないですよね)

今回の問題では、実際に同様に確からしいのは、1を2枚区別して1a, 1bなどとすると、

1a1b 2a2b
1a1b 2b2a
1b1a 2a2b
... などの4! = 24通りです。(n = 2のとき)

然し、よく考えてみると全て2枚なので対称です。ということは、

どの同じ数字の2枚を入れ替えても同じなので、tksmsyshさんのように2^nで割ったペア――即ち#1のような組み合わせは同様に確からしいと言えます。
今度は更に、それらのペアでもAとBを入れ替えたものに注目して、
11-22と22-11や12-21と21-12のようなペア同士を入れ替えただけのものもすべてn!組存在していますから、(2n)!を2^n×n!で割ったものは

A B
11 22
12 12
12 21
…… #2
のように3通りだけ(n = 2の場合)となるのです。(これらは同様に確からしいです。)

これを踏まえて考えると、

いま、nまでの数字があるときの条件を満たすペアの組み合わせ(#2のようなもの)をA_nとします。同様に、n + 1までの数字の時の組もA_{n + 1}組とします。(仮定★)

■ (i) さて、条件を見てみると「ペアの数字は同じか1違い」となりますから、n + 1までの数があるとき必然的にどのようなnでも下のような2組が出来上がるでしょう :

(い) (n, n), (n + 1, n + 1)
(ろ) (n, n + 1), (n, n + 1)
(は) (n, n + 1), (n + 1, n)

注目すべきは、(ろ)と(は)は組み合わせ的には同じでも確率では別と考える点です。(最初の例で示しました。)
これら(い)～(は)の3通りですが、実際にはその前にわんさかあります。でも下が変わっただけで、全体ではA_{n + 1}通りあります。

■ (ii) 今度はここに2枚のn + 2のカードを加えたいと思います。然し、条件からそのようなペアは、

(い1) (n, n), (n + 1, n + 1), (n + 2, n + 2)
(い2）(n, n), (n + 1, n + 2), (n + 1, n + 2)
(い3）(n, n), (n + 1, n + 2), (n + 2, n + 1)
(ろ') (n, n + 1), (n, n + 1), (n + 2, n + 2)
(は') (n, n + 1), (n + 1, n), (n + 2, n + 2)

となりますよね。このような条件を満たす組は当然A_{n + 2}組です。(仮定★通り)
漸化式をたてるときは、前後の変化に着目します。(ろ)(は)型――詰まり(n, n + 1)から始まっていたのは後に(n + 2, n + 2)を付ければいいだけなので、
変化していません。逆に、(い)型は3倍に増殖しています。詰まり、(い)の形が2つ分増えているのです。

ここで、(い)の形は(n, n)で終わっていますが、これはこれを含めた2n枚のカードを組み合わせにしたもので、条件を満たすカードは当然A_n組です。(仮定通り)
従って、増分はA_n × 2ですね。

以上(i)(ii)から、A_{n + 2} = A_{n + 1} + 2A_nです。

あとは、A_1 = 3, A_2 = 5(書き出しました)を利用して漸化式を解きます。恐らくa_n = {2^{n + 2} - (-1)^n}/3かと思われます。
そして、全ての組は前述の通り(2n)!/(2^n×n!)通りでありますから割ればいいです。

参考にして頂けたら幸いです。

お礼

非常に分かりやすいご説明、ありがとうございます。
おかげさまで理解できました。

回答No.1

Tacosan

n が書かれたカードとどのカードが対になるかを考える.

お礼

ご回答ありがとうございました。