状況の変化をある関数で表す問題（順列）

質問

「m個所の送信施設を持つA国から、n個所の受信施設を持つB国へ信号を送る。A国の各施設はB国の施設の中のただ1個所に必ず信号を送るものとし、その送受信は一斉に行われる。いまm≧nとし、B国のどの受信施設もA国のどこかの送信施設からの信号を少なくとも1つは受信する場合を考える。このような送信パターンの数をｆ(m,n)と表す。以下m,nを変化させて考えるとき、次の問いに答えよ。
(1)n=3のときf(m,３)をｍを用いて表せ。
(2)f(m+1,n)をf(m,n)およびf(m,n-1)を用いて表せ。ただしn≧２とする。
(3)f(m+1,m)をmを用いて表せ。」

という長い問題に取り組んでいます
(1)すら解けなくて困っています。
ｍ＝３のときをまず考えました。ｍの3箇所からの送信がnの3箇所に受信されるので、ｍの3箇所の並び替えで3P3＝３！＝６　
ｍ＝４のときはｍの4箇所のうち3箇所を選んで並び替えて残り1箇所がｎの3箇所のうちどれかに送信されるので4P3＊３＝72　
という考え方でいいのでしょうか？
順列や組み合わせや確率がかなり苦手なので全く自信がありません。
(2)(3)は(1)がよくわからないのでできません。

教えていただければ幸いです。
宜しくお願いいたします

回答No.2

age_momo · ベストアンサー

(1)Bの基地が1つだとその組み合わせは1^m=1通りです。
2つだと2^m通りですがそこには全部片方に偏る組み合わせが2通り含まれていますので
2^m-2　となります。
3つだと3^mからこの2つに集中する組み合わせと1つに集中する組み合わせを引きます。その時に3個の中から2個を選ぶ組み合わせ、3個の中から集中する1個を選ぶ組み合わせを掛けるのを忘れずに計算します。
3^m-3C2(2^m-2)-3C1*1^m=3^m-3*2^m+3

(2)#1さんが書いてますが

a)m個で既にn個の基地全てを選択してしまっている場合(f(m,n)通りですね）
(m+1)個目はn個のB基地から自由に選べますからn*f(m,n)通りあります。

b)m個で(n-1)個のB基地を選んでいる(f(m,n-1)通りです)と
(m+1)個目は最後の一つを選ぶ必要があります。→f(m,n-1)通り
ただし、最後に残るB基地はn通りあるのでこれもn*f(m,n-1)通りあります。

その和ですので
f(m+1,n)=n*{f(m,n)+f(m,n-1)}
となります。

(3)f(m+1,m)=m*{f(m,m)+f(m,m-1)}
=m*f(m,m)+m*f(m,m-1)
=m*m!+m*(m-1){f(m-1,m-1)+f(m-1,m-2)}
=m*m!+m(m-1)*(m-1)!+m(m-1)*f(m-1,m-2)
・・・
=m*m!+(m-1)*m!+(m-2)*m!+…+1*m!
=m!{m+(m-1)+(m-2)+…+1}
=m/2*(m+1)!

お礼

お二方、回答ありがとうございました。
丁寧に回答いただき本当にたすかりました

回答No.1

kony0

異なるm個の玉を、異なるn個の箱に入れるときに、どの箱にも少なくとも１つの玉が入っている入れ方は何通りあるか？という問題ですね。特に長い問題ではないです。(1)はよく見る問題ですが、決して簡単ではありません。ちなみに(1)と(2)(3)は直接関係なさそうです。(1)は表記に慣れ親しむ観点の小問と思われます。

(1)とりあえず、m個の玉をでたらめに箱に入れてみましょう。
そうすると、1つの箱や2つの箱に玉が集中する場合があるので、それを取り除きます。

(2)f(m+1,n)の考え方は、まずm個の玉とn個の箱のある状況を考えて、それにm+1個目の玉を入れようと考える手法です。
・m個の玉で、n個の箱のいずれにも玉が入っている→m+1個目の玉はn個の箱のどこに入れてもよい。
・m個の玉で、n個の箱のうち、「どれか１つだけ」玉が入っていない→その箱はどれなんだろう？m+1個目はその箱に入れないといけませんね。ところでm個の玉は、その箱以外のn-1個の箱に、いずれも少なくとも１つ以上入っています。

(3)は(2)で作った漸化式に、ご推察のとおりのf(m,m)=m!を用いて２項間漸化式をとくことになりそうですが、難しい漸化式ですね・・・