写像12相(3)

写像12相

3, 9, 7を解説します。

3 n個の区別された玉をk個の区別された箱に、全ての箱の玉が一つ以上になるように入れる方法

チーム分けの問題だと考えると分かりやすい。

例えば、$${4}$$人をチームA, B, Cの$${3}$$チームに分ける総数を求める。
ただし、"メンバー$${0}$$人のチーム"は作らないとする。

グラウンドにA, B, Cというエリアを作って、単純に$${4}$$人を$${3}$$エリアに振り分ける方法は、$${1}$$人目はA, B, Cの$${3}$$エリアに振り分けることができるので$${3}$$通り、その各々について$${2}$$人目もA, B, Cの$${3}$$エリアに振り分けることができるので$${3}$$通り、……、その各々について$${4}$$人目もA, B, Cの$${3}$$エリアに振り分けることができるので$${3}$$通り、つまり$${3 \times 3 \times 3 \times 3=81}$$通り。

この$${81}$$通りから、誰もいないエリアが存在する場合の数を除いていく。

仮にエリアAには誰もいないと仮定すると、エリアB, Cに$${4}$$人を振り分けていくので、先ほどの$${3 \times 3 \times 3 \times 3}$$の$${3}$$を$${2}$$に置き換えた$${2 \times 2 \times 2 \times 2 = 16}$$通りがエリアAには誰もいない総数である。

同じように、エリアBには誰もいない総数も$${16}$$通り、エリアCには誰もいない総数も$${16}$$通り。

したがって、$${81}$$通りから$${3\times 16}$$通りを除けば答えを求められる、と一見そう思う。

しかし、$${3\times 16}$$通りは、例えばエリアA, B両方に誰もいない総数を重複してカウントしている。

エリアA, B両方に誰もいない総数は、$${4}$$人全員をエリアCに突っ込む総数なので$${1}$$通り。

同じように、エリアB, C両方に誰もいない総数も$${1}$$通り、エリアC, A両方に誰もいない総数も$${1}$$通り。

したがって、$${3\times 16}$$通りを調整した$${3\times 16 - 3\times 1}$$通りを$${81}$$通りから除いたものが真の答えである。

ちなみに、今回の分け方ではエリアA, B, C全てに誰もいない場合は不可能なので考慮しない。

以上より、$${4}$$人を$${3}$$エリアA, B, Cに振り分ける総数から誰もいないエリアが存在する場合の数を除いたもの、即ち$${4}$$人をチームA, B, Cの$${3}$$チームに分ける総数は$${81 - (3\times 16 - 3\times 1 ) = 36}$$通り。

この考え方を一般化する。

$${n}$$個の区別された玉を$${k}$$個の区別された箱に、全ての箱の玉が一つ以上になるように入れる方法を求める。

まず、玉の数$${0}$$の箱を許容した場合は、$${k^n}$$通り。

次に、玉の数$${0}$$の箱が存在するように玉を箱に入れる方法の総数を求める。

どの箱が玉の数$${0}$$であるかに着目する。

少なくとも1つの箱の玉の数が$${0}$$の場合は、着目している箱以外に玉を入れる方法が$${(k-1)^n}$$通りで、どの箱に着目するかが$${{}_k C_1}$$通りあるので$${{}_k C_1 \cdot (k-1)^n}$$通り。

少なくとも2つの箱の玉の数が$${0}$$の場合は、着目している箱以外に玉を入れる方法が$${(k-2)^n}$$通りで、どの箱に着目するかが$${{}_k C_2}$$通りあるので$${{}_k C_2 \cdot (k-2)^n}$$通り。

：
：

同じように、少なくとも$${k-1}$$つの箱の玉の数が$${0}$$の場合は、着目している箱以外に玉を入れる方法が$${1^n}$$通りで、どの箱に着目するかが$${{}_k C_{k-1}}$$通りあるので$${{}_k C_{k-1} \cdot 1^n}$$通り。

少なくとも$${k}$$つの箱の玉の数が$${0}$$の場合は不可能なので考慮しない。

$${{}_k C_1 \cdot (k-1)^n, {}_k C_2 \cdot (k-2)^n, \dots, {}_k C_{k-1} \cdot 1^n}$$から玉の数$${0}$$の箱が存在するように玉を箱に入れる方法の総数を正確に求めるわけだが、結論から言うと以下の式で導き出せる。
$${{}_k C_1 \cdot (k-1)^n - {}_k C_2 \cdot (k-2)^n, \dots, + (-1)^{k-1} {}_k C_{k-1} \cdot 1^n}$$

理由は、この式にはどんな箱の数に対しても、共通部分が丁度$${1}$$回カウントされるから。

どういうことかというと、例えばA, B, C, Dと名付けた特定の箱$${4}$$つに玉が$${1}$$個も入っていない状況Xが何回カウントされるかを考える。

便宜的に、$${{}_k C_1 \cdot (k-1)^n - {}_k C_2 \cdot (k-2)^n, \dots, + (-1)^{k-1} {}_k C_{k-1} \cdot 1^n}$$を式Aとし、式A中の$${{}_k C_{i} \cdot (k-i)^n}$$を第$${i}$$項と呼ぶことにする。

第$${1}$$項では、少なくとも箱Aに玉が全く入っていない場合に状況Xが一回登場する、少なくとも箱Bに玉が全く入っていない場合に状況Xが一回登場する、……、少なくとも箱Dに玉が全く入っていない場合に状況Xが一回登場する、したがって状況Xが$${{}_4 C_{1}}$$回カウントされる。

第$${2}$$項では、少なくとも箱A, Bに玉が全く入っていない場合に状況Xが一回登場する、少なくとも箱A, Cに玉が全く入っていない場合に状況Xが一回登場する、……、少なくとも箱C, Dに玉が全く入っていない場合に状況Xが一回登場する、したがって状況Xが$${{}_4 C_{2}}$$回カウントされる。

第$${3}$$項では、少なくとも箱A, B, Cに玉が全く入っていない場合に状況Xが一回登場する、少なくとも箱A, B, Dに玉が全く入っていない場合に状況Xが一回登場する、……、少なくとも箱B, C, Dに玉が全く入っていない場合に状況Xが一回登場する、したがって状況Xが$${{}_4 C_{3}}$$回カウントされる。

第$${4}$$項では、少なくとも箱A, B, C, Dに玉が全く入っていない場合に状況Xが一回登場する。したがって状況Xが$${{}_4 C_{4}}$$回カウントされる。

式A上では状況Xが$${{}_4 C_{1} - {}_4 C_{2} + {}_4 C_{3} - {}_4 C_{4}}$$回カウントされていることになり、計算すると$${4 - 6 + 4 -1 = 1}$$になる。

名付ける4つの箱を変えてA, B, C, Eとしても同じように式A中のカウントは$${1}$$であるし、名付ける箱の数を3にしてA, B, Cとしても式A中のカウントは$${{}_3 C_{1} - {}_3 C_{2} + {}_3 C_{3} = 3 - 3 + 1 = 1}$$回となる。

こうなると、どのような$${m}$$に対しても常に$${{}_m C_{1} - {}_m C_{2} - {}_m C_{3} + \dots + (-1)^{m-1} {}_m C_{m} = 1}$$が成り立つかが気になるが、これは二項定理から成立が証明される。
$${0}$$
$${=(1-1)^m}$$
$${={}_m C_{0} - {}_m C_{1} + {}_m C_{2} - \dots + (-1)^{m} {}_m C_{m}}$$
$${=1 - ({}_m C_{1} - {}_m C_{2} + {}_m C_{3} - \dots + (-1)^{m-1} {}_m C_{m})}$$
したがって、$${{}_m C_{1} - {}_m C_{2} + {}_m C_{3} - \dots + (-1)^{m-1} {}_m C_{m} = 1}$$

ゆえに、$${n}$$個の区別された玉を$${k}$$個の区別された箱に、全ての箱の玉が一つ以上になるように入れる方法の正確な総数は$${{}_k C_1 \cdot (k-1)^n - {}_k C_2 \cdot (k-2)^n + \dots + (-1)^{k-1} {}_k C_{k-1} \cdot 1^n}$$通り。

以上より、$${n}$$個の区別された玉を$${k}$$個の区別された箱に、全ての箱の玉が一つ以上になるように入れる方法は
$${k^n - ({}_k C_1 \cdot (k-1)^n - {}_k C_2 \cdot (k-2)^n \dots + (-1)^{k-1} {}_k C_{k-1} \cdot 1^n)}$$
$${= k^n - {}_k C_1 \cdot (k-1)^n + {}_k C_2 \cdot (k-2)^n \dots + (-1)^{k} {}_k C_{k-1} \cdot 1^n}$$通り。

9 n個の区別された玉をk個の区別しない箱に、全ての箱の玉が一つ以上になるように入れる方法

ケース3の総数から箱の区別を解除すればよい。

$${k}$$個の箱の区別の解除方法は$${k!}$$通りあるので、ケース3の総数を$${k!}$$で割ればよい。
$${\frac{1}{k!}( k^n - {}_k C_1 \cdot (k-1)^n + {}_k C_2 \cdot (k-2)^n \dots + (-1)^{k} {}_k C_{k-1} \cdot 1^n)}$$

7 n個の区別された玉をk個の区別しない箱に入れる方法

ケース9で玉数0の箱が許容されたものなので、ケース9において$${k}$$を$${1}$$から$${k}$$まで足し合わせたものが求める総数です。

$${\sum_{i=1}^k\frac{1}{i!}( i^n - {}_i C_1 \cdot (i-1)^n + {}_i C_2 \cdot (i-2)^n \dots + (-1)^{i} {}_i C_{i-1} \cdot 1^n)}$$