順列の問題

質問

ある部署では、一年間通じて活動するプロジェクトチーム(以下、チーム)をいくつか構成することになっているが、これらのチームは次のア、イ、ウの要件に従って構成されている。

ア：チームごとの多様性を発揮させるため、構成メンバーが全員同じチームは作らない。

イ：チーム間の情報共有のため、どの2つのチームの構成メンバーを見ても、必ず共通する人が少なくとも1名はいる。

ウ：チームは1名で構成してもよい。

この部署には昨年8名が所属していたが、今年は1名増えて9名となった。このとき、今年構成できるチームの数は昨年よりいくつ増えたか。

解き方は、
２の７乗＝１２８
２の８乗＝２５６
２５６－１２８＝１２８(通り)

故に、１２８通り増えた

と書いてあるのですが、なぜこういう解き方になるのかわかりません。順列は苦手なので、分かりやすく教えていただけたら幸いです。よろしくお願いします。

回答No.1

kumipapa · ベストアンサー

１名のみのチームは、要件イから１チームしかできません。例えばＡさん１名のみで１チームを作ったら、他の人は１名だけのチームは作れません。また、Ａさん１名のチームを作ったら、他の複数名で構成されるチームはすべてＡさんをメンバーにしなければなりません。

１名のみのチームを作らなかったとし、２名で構成されるチームを考え、ＡさんとＢさんで１チームを作ったとします。すると、その他の２名構成のチームには、ＡさんかＢさんが入っていなければなりませんから、例えば、ＡさんとＣさんでもう一つチームを作ります。次に、ＢさんとＣさんでもう１チーム作ってもよいのですが、そうすると、A,B,C以外の人は２名チームには加われず、２名構成のチームは３チームしかできなくなってしまいます。ということで、人数が３名よりも多い場合、２名構成のチーム数は、決まった１名＋他の１名という組み合わせが最大数となります。全体が８名ならば７チーム、９名ならば８チームです。

さらに３名構成のチームを、２名構成のチームのことまで念頭において考えると・・・、と順次考えていくと、結局、イの要件を満足させた場合の最大のチーム数は、「全てのチームに加わる者を１名決めて、他の人々をどのように組み合わせるか」で決まるチームの数になるようです。（本当にそれが最大数になるのかどうかは、真面目に吟味していませんが。）

ということで、全てのチームのメンバーの構成は、まず１名決めて、残りの者おのおのがチームに入るか入らないかの２択の組み合わせで表すことができます。ですから、できるチームの数は、
人数が８名の場合　・・・　２^(8-1) ＝ ２^7 ＝ 128 チーム
人数が９名の場合　・・・　２^(9-1) ＝ ２^8 ＝ 256 チーム
となるのでしょう。

お礼

どうもありがとうございます。おかげさまで理解できました。