数学ナビゲーター掲示板 [One Topic All View / Re[8]: 順列 / Page: 0]

数学ナビゲーター掲示板
(現在過去ログ4 を表示中)

[ 最新記事及び返信フォームをトピックトップへ ]

■44254 / inTopicNo.1)

　順列

□投稿者/ かほり一般人(1回)-(2011/11/20(Sun) 12:13:29)

nとmはともに1以上の整数とする。
○が書かれたカードがn+m枚、×が書かれたカードがn-m枚ある。これら2n枚のカードを、以下の規則に従って横一列に並べる。このとき、並べ方の総数を求めなさい。

規則
1≦k≦2nを満たす任意の整数kに対し、左から数えて1番目のカードからk番目のカードまでに含まれる○が書かれたカードの枚数が、常に×が書かれた枚数より多い。

左2枚は○で、次は○か×で、○の場合は次がまた○か×で、×の場合は次は自動的に○で、…などと場合分けしていったんですがとても解けそうにないです。
解き方を詳しく教えてください。お願いします。

引用返信/返信 [メール受信/OFF] 削除キー/

■44255 / inTopicNo.2)

　Re[1]: 順列

▲▼■

□投稿者/ vanilla bonica. 一般人(48回)-(2011/11/20(Sun) 16:55:23)

http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0
これが参考になると思います。

引用返信/返信 [メール受信/OFF] 削除キー/

■44256 / inTopicNo.3)

　Re[1]: 順列

▲▼■

□投稿者/ かほり一般人(2回)-(2011/11/20(Sun) 21:48:09)

ご紹介いただいたページを見ましたが、この問題と関係あるんですか？すみませんがそこすらわかりません…

引用返信/返信 [メール受信/OFF] 削除キー/

■44257 / inTopicNo.4)

　Re[2]: 順列

▲▼■

□投稿者/ らすかる一般人(23回)-(2011/11/20(Sun) 22:29:46)

関係は大いにありますが、そのページには解き方は書かれていませんね。
xy平面上で最初原点(0,0)にいて、左から順にカードを見ていって
○なら右、×なら上に進むことにします。
ただし最初は○、つまり(0,0)→(1,0)に進むものとします。
○がn+m枚、×がn-m枚ですから、最終的には(n+m,n-m)に到達しますが、
問題の条件に合う並べ方の場合は
「直線y=xに一度も接することなく(n+m,n-m)に到達する」
となります。
このパターン数を計算するには、
「条件を無視したパターンの数」－「条件に合わないパターンの数」
として計算します。
「条件を無視したパターンの数」は(2n-1)C(n-m)ですね。
「条件に合わないパターンの数」を計算するには、
「条件に合わないパターンを、最初に直線y=xに接した時以降の進行方向を
　直線y=xに関して反転して（つまり○なら上、×なら右に進む）考える」
として計算します。
そうすると最終到達点が(n-m,n+m)になりますから、
「条件に合わないパターンの数」は(2n-1)C(n+m)となり、
求める並べ方の数は
(2n-1)C(n-m)-(2n-1)C(n+m)=(2m)(2n-1)!/{(n-m)!(n+m)!}
となります。（ただしnCrはn＜rのとき0とする）

引用返信/返信 [メール受信/OFF] 削除キー/

■44258 / inTopicNo.5)

　Re[3]: 順列

▲▼■

□投稿者/ かほり一般人(3回)-(2011/11/21(Mon) 00:49:35)

らすかる様　解説をありがとうございます。

＞「条件に合わないパターンの数」を計算するには、
「条件に合わないパターンを、最初に直線y=xに接した時以降の進行方向を
　直線y=xに関して反転して（つまり○なら上、×なら右に進む）考える」
として計算します。

何度読んでもここがどういう考え方なのか分からないです。
y≧xの部分を通る場合が余事象になるのはわかりますが、そこからなぜ(n-m,n+m)に到着する場合が余事象になるのでしょうか。

引用返信/返信 [メール受信/OFF] 削除キー/

■44259 / inTopicNo.6)

　Re[4]: 順列

▲▼■

□投稿者/ らすかる一般人(24回)-(2011/11/21(Mon) 01:20:02)

例えばn=3,m=1の場合を考えます。○が4枚、×が2枚です。
（以下の説明は図を書いて考えて下さいね。）
条件を無視した場合の(4,2)に到達するパターン（最初は右）は
右右右右上上
右右右上右上
右右右上上右
右右上右右上
右右上右上右
右右上上右右
右上右右右上
右上右右上右
右上右上右右
右上上右右右
の10通りですね。このうちy=xにぶつかるのは後ろの5つで、
y=xにぶつかった後の「右」「上」を反転すると
右右上上右右 → 右右上上上上
右上右右右上 → 右上上上上右
右上右右上右 → 右上上上右上
右上右上右右 → 右上上右上上
右上上右右右 → 右上右上上上
になります。これは最初が「右」で(2,4)に到達するすべての
パターンです。
「y=xにぶつかったところ」から(4,2)までの経路を
y=xに関して反転すれば、(2,4)に到達しますよね。
逆に、(1,0)から(2,4)に到達するすべてのパターンは、
y=xにぶつかったところから先をy=xに関して反転すれば
(4,2)に到達します。
つまり、
「(1,0)から(4,2)に到達するパターンのうちy=xにぶつかるもの」と
「(1,0)から(2,4)に到達するパターン」は一対一に対応していますので、
上に書いたように計算できるということです。

引用返信/返信 [メール受信/OFF] 削除キー/

■44260 / inTopicNo.7)

　Re[5]: 順列

▲▼■

□投稿者/ らすかる一般人(25回)-(2011/11/21(Mon) 01:22:41)

追記
上の「y=xにぶつかる」というのは
「y=xに初めてぶつかる」という意味です。
2回以上ぶつかる場合、2回目以降は関係なく、
1回目にぶつかったところで反転します。

引用返信/返信 [メール受信/OFF] 削除キー/

■44261 / inTopicNo.8)

　Re[6]: 順列

▲▼■

□投稿者/ かほり一般人(4回)-(2011/11/21(Mon) 14:13:28)

らすかる様　お詳しい解説をしていただきましてありがとうございました。

y=xに初めてぶつかったところ以降で反転させると、条件に合わない経路はすべて定点(n-m,n+m)に集まるので、(1,0)→(n-m,n+m)の経路の総数が条件に合わない総数ということになるんですね。大変よくわかりました。

経路の問題に置き換えるところや反転させるなんてすごいアイデアですね!数学の解説ではじめてふるえました^^どうやって反転させればうまくいくと思いつかれたんですか？参考に教えていただけないでしょうか？

引用返信/返信 [メール受信/OFF] 削除キー/

■44262 / inTopicNo.9)

　Re[7]: 順列

▲▼■

□投稿者/ らすかる一般人(26回)-(2011/11/21(Mon) 16:16:17)

残念ながら自分で思いついたわけではなく、どこかで使われていたアイデアです。
この問題ではy=xで反転しましたが、問題によって反転する場所が変わりますので
（基本的に条件に合わなくなる位置で反転）似たような問題に遭遇したら
応用してみて下さい。

引用返信/返信 [メール受信/OFF] 削除キー/

■44275 / inTopicNo.10)

　Re[8]: 順列

▲▼■

□投稿者/ かほり一般人(5回)-(2011/11/23(Wed) 23:24:15)