|
uchinyan |
|
2005/03/12：ごめんなさい。最初の証明は間違っていました。訂正します。
#24690の解法は、実は、#24688で失敗したと言った漸化式へのトライの副産物です。 考え直して、漸化式、A(n+1) = C(n,1) * A(n) + C(n,2) * A(n-2) を#24690流に証明しておきます。 #24690を一般化すると、1 〜 (n+1) までの数字が一つずつそれぞれに書かれたカード (n+1) 枚の組が2組あることになります。 1 以外を、a, b, c, d, e, ..., ただし a > b、a > c とします。 A(n+1) は、(n+1) 個の 1, a, b, c, d, e, ... の数字の組の2組から、条件を満たす (n+1) 個の数を作る場合の数になります。 基本的には a, b, c, d, e, ... に 1 を追加すればいいのですが、以下では、#24690を少し改良して、次のように考えます。 １）a1, b1, ab 及び c, d, e, ... の組合せの場合 まず、1 と a, b との組合せは、n(n-1)/2 = C(n,2) 通りになるので、a1, b1, ab で C(n,2) 通り。残りの (n-2) 個で A(n-2) 通り。 したがって、C(n,2) * A(n-2) 通り。 ２）a1, b1 だが ab を作らず c, d, e, ... と混ぜて組み合わせる場合 1 を除いた部分が A(n) 程度なのですが、ab を作らないので、これを除く必要があります。 今、A(n) において、作られている n 個の数のうちから一つを取り出し、これを ab とします。 これを取り去って、代わりに、a1, b1 を追加すればいいわけです。これが求める数の組になります。 ただ、このときの場合の数の数え方が難しく失敗していました (^^; これは、ちょっと複雑ですが、次のような「トリック」を行えばいいようです。 a は、A(n) で、他の数字と ab 以外の数を一つ作っています。この数字を c とし、作っている数を ac とします。 ここで場合の数を数えるために、ac に対して c1 という数を1:1に対応させます。 すると、この1:1対応によって、a1 以外は、1, b, c, d, e ... の n 個の数字で構成されていることになります。 このときの場合の数は、a1 以外が A(n) 通り、a1 は a の選択で C(n,1) 通り、結局 C(n,1) * A(n) 通りになります。 （なお、実際に構成される数は、c1 を ac に置き換えたものなので要注意。） １)及び２）から、結局、両方を合わせて、A(n+1) = C(n,1) * A(n) + C(n,2) * A(n-2) になります。 正直言って、ちょっとややこしいですが、小学名探偵さんの#24689と比較すると、 １）は（２）の「３角形の分離」の部分、２）は（１）のノードを付加する部分に対応します。 |
|
ネコの住む家
3月12日（土） 14:12:04
MAIL:uchi@sco.bekkoame.ne.jp 24692 |