twelvefold

<p>
以降で「人」と書けば集合の要素を区別し、明示せず「個」と書けば区別しないものとする。まず、問題を列挙する。
</p>
<ol>
<li>\(n\) 人を区別のある \(k\) 部屋に分ける場合の数を求めよ。
<ol>
<li>空室があってもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\(n=4, k=6\) の場合：<br/>
</li>
<li>空室があってもよいが、部屋には一人ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\(n > k\) の場合：<br/>
</li>
<li>空室があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\(n < k\) の場合：<br/>
</li>
<li>空室があってはならず、部屋には一人ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\(n \neq k\) の場合：<br/>
</li>
</ol>
</li>
<li>\(n\) 個を \(k\) 人に分ける場合の数を求めよ。
<ol>
<li>配分なしの人がいてもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\(n=4, k=6\) の場合：<br/>
</li>
<li>配分なしの人がいてもよいが、一人一個ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\(n > k\) の場合：<br/>
</li>
<li>全員に配分しなくてはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\(n < k\) の場合：<br/>
</li>
<li>全員に配分しなくてはならなず、一人一個ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\(n \neq k\) の場合：<br/>
</li>
</ol>
</li>
<li>\(n\) 人を区別のない \(k\) 部屋に分ける場合の数を求めよ。
<ol>
<li>空室があってもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\(n=4, k=6\) の場合：<br/>
</li>
<li>空室があってもよいが、部屋には一人ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\(n > k\) の場合：<br/>
</li>
<li>空室があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\(n < k\) の場合：<br/>
</li>
<li>空室があってはならず、部屋には一人ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\(n \neq k\) の場合：<br/>
</li>
</ol>
</li>
<li>\(k\) 個を区別のない \(n\) 個の壺に分ける場合の数について考察せよ。
<ol>
<li>空壺があってもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\(n=4, k=6\) の場合：<br/>
</li>
<li>空壺があってもよいが、壺には一個ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\(n > k\) の場合：<br/>
</li>
<li>空壺があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\(n < k\) の場合：<br/>
</li>
<li>空壺があってはならず、壺には一個ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\(n \neq k\) の場合：<br/>
</li>
</ol>
</li>
</ol>
<p>
次に、これらの回答を簡単に列挙する。
</p>
<ol>
<li>\(n\) 人を区別のある \(k\) 部屋に分ける場合の数を求めよ。
<ol>
<li>空室があってもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\[
k^n = 3^4 = 81
\]
\(n=4, k=6\) の場合：<br/>
\[
k^n = 6^4 = 1296
\]
</li>
<li>空室があってもよいが、部屋には一人ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\[
\begin{aligned}
k^{\underline{n}} = \permu{k}{n} = \permu{6}{4} = 6\cdot 5\cdot 4\cdot 3 &= 360\\
n!\dbinom{k}{n} = 4!\dbinom{6}{4} = 24\cdot 15 &= 360
\end{aligned}
\]
\(n > k\) の場合：<br/>
\[
0
\]
</li>
<li>空室があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\[
k!\dstirlii{n}{k} = 3!\dstirlii{4}{3} = 6\cdot 6 = 36
\]
<small>
ここで、第２種スターリング数 \(\stirlii{n}{k}\) は、
\[
\begin{aligned}
\dstirlii{n}{k} &= \frac1{k!}\sum_{i=1}^{k}(-1)^{k-i}\dbinom{k}{i}i^n =\\
\dstirlii{4}{3} &= \frac1{3!}\left(
(-1)^{3-1}\dbinom{3}{1}1^4 +
(-1)^{3-2}\dbinom{3}{2}2^4 +
(-1)^{3-3}\dbinom{3}{3}3^4
\right)\\
&= \frac1{3!}(3 - 3\cdot 16 + 81) = 6\\\end{aligned}
\]
</small>
\(n < k\) の場合：<br/>
\[
0
\]
</li>
<li>空室があってはならず、部屋には一人ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\[
k! = 4! = 24
\]
\(n \neq k\) の場合：<br/>
\[
0
\]
</li>
</ol>
</li>
<li>\(n\) 個を \(k\) 人に分ける場合の数を求めよ。
<ol>
<li>配分なしの人がいてもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\[
\begin{aligned}
\repecombi{k}{n} &= \combi{k+n-1}{n} = \dbinom{k+n-1}{n} =\\
\repecombi{3}{4} &= \combi{3+4-1}{4} = \dbinom{3+4-1}{4} = \dbinom{6}{4} = 15
\end{aligned}
\]
\(n=4, k=6\) の場合：<br/>
\[
\begin{aligned}
\repecombi{k}{n} &= \combi{k+n-1}{n} = \dbinom{k+n-1}{n} =\\
\repecombi{6}{4} &= \combi{6+4-1}{4} = \dbinom{6+4-1}{4} = \dbinom{9}{4} = 126
\end{aligned}
\]
</li>
<li>配分なしの人がいてもよいが、一人一個ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\[
\combi{k}{n} = \dbinom{k}{n} = \dbinom{6}{4} = 15
\]
\(n > k\) の場合：<br/>
\[
0
\]
</li>
<li>全員に配分しなくてはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\[
\combi{n-1}{n-k} = \dbinom{n-1}{n-k} = \dbinom{n-1}{k-1} = \dbinom{4-1}{3-1} = 3
\]
\(n < k\) の場合：<br/>
\[
0
\]
</li>
<li>全員に配分しなくてはならなず、一人一個ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\[
1
\]
\(n \neq k\) の場合：<br/>
\[
0
\]
</li>
</ol>
</li>
<li>\(n\) 人を区別のない \(k\) 部屋に分ける場合の数を求めよ。
<ol>
<li>空室があってもよい。<br/>
\(n=4, k=3\) の場合：<br/>
\[
\begin{aligned}
B(n, k) &= \sum_{i=1}^{k}\dstirlii{n}{i} =\\
B(4, 3) &= \sum_{i=1}^{3}\dstirlii{4}{i} = \dstirlii{4}{1} + \dstirlii{4}{2} + \dstirlii{4}{3} = 1 + 7 + 6 = 14
\end{aligned}
\]
\(n=4, k=6\) の場合：<br/>
\[
\begin{aligned}
B(n, k) &= \sum_{i=1}^{k}\dstirlii{n}{i} =\\
B(4, 6) &= \sum_{i=1}^{6}\dstirlii{4}{i}\\ &= \dstirlii{4}{1} + \dstirlii{4}{2} + \dstirlii{4}{3} + \dstirlii{4}{4} + \dstirlii{4}{5} + \dstirlii{4}{6}\\ &= 1 + 7 + 6 + 1 + 0 + 0 + 0 = 15
\end{aligned}
\]
</li>
<li>空室があってもよいが、部屋には一人ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\[
1
\]
\(n > k\) の場合：<br/>
\[
0
\]
</li>
<li>空室があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\[
\dstirlii{n}{k} = \dstirlii{4}{3} = 6
\]
\(n < k\) の場合：<br/>
\[
0
\]
</li>
<li>空室があってはならず、部屋には一人ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\[
1
\]
\(n \neq k\) の場合：<br/>
\[
0
\]
</li>
</ol>
</li>
<li>\(k\) 個を区別のない \(n\) 個の壺に分ける場合の数について考察せよ。
<ol>
<li>空壺があってもよい。<br/>
\(n=4, k=3\) の場合：
\(n=4, k=6\) の場合：<br/>
\[
\text{これは未解決問題である。}
\]
</li>
<li>空壺があってもよいが、壺には一個ずつ。<br/>
\(n=4, k=6\) の場合：<br/>
\[
1
\]
\(n > k\) の場合：<br/>
\[
0
\]
</li>
<li>空壺があってはならない。<br/>
\(n=4, k=3\) の場合：<br/>
\[
\text{これは未解決問題である。}
\]
\(n < k\) の場合：<br/>
\[
0
\]
</li>
<li>空壺があってはならず、壺には一個ずつ。<br/>
\(n=4, k=4\) の場合：<br/>
\[
1
\]
\(n \neq k\) の場合：<br/>
\[
0
\]
</li>
</ol>
</li>
</ol>
<p>
以上をまとめると下表の通り。
<table class="table table-sm table-bordered text-center small">
<thead>
<tr>
<th class="align-middle"><span style="white-space: nowrap;">\(n\) 個の</span>区別</th>
<th class="align-middle"><span style="white-space: nowrap;">\(k\) 組の</span>区別</th>
<th class="align-middle">各組 \(0\le\) 個 <span style="white-space: nowrap;">(\(n\lt k\) の場合も含む)</span></th>
<th class="align-middle">各組 \(0\text{ or }1\) 個 <span style="white-space: nowrap;">(\(n\gt k\) の場合 \(0\))</span></th>
<th class="align-middle">各組 \(1\le\) 個 <span style="white-space: nowrap;">(\(n\lt k\) の場合 \(0\))</span></th>
<th class="align-middle">各組 \(1\) 個 <span style="white-space: nowrap;">(\(n\neq k\) の場合 \(0\))</span></th>
</tr>
</thead>
<tbody>
<tr>
<td class="align-middle"><span style="white-space: nowrap;">する</span></td>
<td class="align-middle"><span style="white-space: nowrap;">する</span></td>
<td class="align-middle">\(k^n\)</td>
<td class="align-middle">\(n!\binom{k}{n} = \permu{k}{n}\)</td>
<td class="align-middle">\(k!\stirlii{n}{k}\)</td>
<td class="align-middle">\(k!\)</td>
</tr>
<tr>
<td class="align-middle"><span style="white-space: nowrap;">しない</span></td>
<td class="align-middle"><span style="white-space: nowrap;">する</span></td>
<td class="align-middle">\(\binom{k+n-1}{n} = \repecombi{k}{n}\)</td>
<td class="align-middle">\(\binom{k}{n}\)</td>
<td class="align-middle">\(\binom{n-1}{n-k} = \binom{n-1}{k-1}\)</td>
<td class="align-middle">\(1\)</td>
</tr>
<tr>
<td class="align-middle"><span style="white-space: nowrap;">する</span></td>
<td class="align-middle"><span style="white-space: nowrap;">しない</span></td>
<td class="align-middle">\(\sum_{i=1}^{k}\stirlii{n}{i} = B(n, k)\)</td>
<td class="align-middle">\(1\)</td>
<td class="align-middle">\(\stirlii{n}{k}\)</td>
<td class="align-middle">\(1\)</td>
</tr>
<tr>
<td class="align-middle"><span style="white-space: nowrap;">しない</span></td>
<td class="align-middle"><span style="white-space: nowrap;">しない</span></td>
<td class="align-middle"><span style="white-space: nowrap;">未解決</span></td>
<td class="align-middle">\(1\)</td>
<td class="align-middle"><span style="white-space: nowrap;">未解決</span></td>
<td class="align-middle">\(1\)</td>
</tr>
</tbody>
</table>
これらの列挙された問題について、以下で詳説する。
</p>

<h3>1.1. 重複順列 \(k\)-sequence in \(n\), composition of \(\le n\) with \(k\) subsets</h3>
<p>
重複順列は以下のように表される。
\[
n^k
\]
例えば、\(n=4, k=2\) であれば \(4^2 = 16\) である。
例えば、\(n=3, k=3\) であれば \(3^3 = 27\) である。
</p>
<p>
また、\(k\) 桁の \(n\) 進数が取りうる場合の数を表している。例えば、\(n=2, k=8\) であれば \(2^8 = 256\) である。
</p>
<p>
また、\(k\) 人を区別のある \(n\) 個以下の組に分ける場合の数を表している。
</p>

<h3>1.2. 順列 \(k\)-permutation of \(n\)</h3>
<p>
順列は、日本の初等教育では \(\permu{n}{k}\) のように表され、これは下降階乗冪 \(n^{\underline{k}}\) に等しい。
\[
\permu{n}{k} = n^{\underline{k}} = \prod_{i=1}^{k}(n-i+1) =
n(n-1)(n-2)\cdots(n-k+1)
\]
例えば、\(n=4, k=2\) であれば \(4^{\underline{2}} = 12\) である。
例えば、\(n=3, k=3\) であれば \(3^{\underline{3}} = 6\) である。
</p>
<p>
また、\(k\) 人を区別のある \(n\) 個以下の組に高々１人ずつ分ける場合の数を表している。但し、\(k\le n\) でなければ \(0\) である。
</p>
<h4>順列の階乗表示</h4>
<p>
ここで、\(n^{\underline{k}}(n-k)! = n!\) であることから、以下のように表せる。
\[
\permu{n}{k} = n^{\underline{k}} = \frac{n!}{(n-k)!} = k!\dbinom{n}{k} = k!(\combi{n}{k})
\]
</p>

<h3>1.3. 全射 composition of \(k\) with \(n\) subsets</h3>
<p>
\(n\) 人を区別のある \(k\) 個の組に分ける場合の数は階乗 \(k!\) と第２種スターリング数 \(\stirlii{n}{k}\) の積で表される。
\[
k!\dstirlii{n}{k}
\]
\[
\dstirlii{n}{k} =
\frac1{k!}\sum_{i=1}^{k}(-1)^{k-i}\dbinom{k}{i}i^n
\]
例えば、\(n=4, k=2\) であれば \(2!\dstirlii{4}{2} = 14\) である。
例えば、\(n=3, k=3\) であれば \(3!\dstirlii{3}{3} = 6\) である。
</p>

<h3>1.4. 階乗 composition of \(n\) with \(k=n\) subsets</h3>
<p>
\(n\) 人を区別のある \(k\) 個の組に１人ずつ分ける場合の数は階乗 \(k!\) で表される。但し、\(n = k\) でなければ \(0\) である。
\[
k!
\]
例えば、\(n=4, k=2\) であれば \(0\) である。
例えば、\(n=3, k=3\) であれば \(3! = 6\) である。
</p>

<h3>2.1. 重複組み合わせ \(k\)-multisubset of \(n\)</h3>
<p>
重複組み合わせは、日本の初等教育では \(\repecombi{n}{k}\) のように表され、\(\combi{n+k-1}{k}\) と等しい。
\[
\repecombi{n}{k} = \combi{n+k-1}{k} = \dbinom{n+k-1}{k}
\]
例えば、\(n=4, k=2\) であれば \(\repecombi{4}{2} = \binom{4+2-1}{2} = 10\) である。また、二項係数の性質
\(
\binom{n}{k} = \binom{n}{n-k}
\)
であることから、以下も成り立つ。
\[
\dbinom{n+k-1}{k} = \dbinom{n+k-1}{n-1}
\]
例えば、\(n=4, k=2\) であれば \(\repecombi{4}{2} = \binom{4+2-1}{4-1} = 10\) である。
例えば、\(n=3, k=3\) であれば \(\repecombi{3}{3} = \binom{3+3-1}{3} = \binom{3+3-1}{3-1} = 10\) である。
</p>
<p>
また、\(k\) 個を区別のある \(n\) 個以下の組に分ける場合の数を表している。これは、\(k\) 個と \(n-1\) 個の仕切りを一列に並べる場合の数と等しい。
</p>
<p>
また、\(\sum_{i=1}^nx_i = k\) の非負整数解の個数が \(\repecombi{n}{k}\) である。例えば、\(n=4, k=6\) であれば \(\repecombi{4}{6} = \binom{4+6-1}{6} = \binom{9}{6} = 84\) である。
</p>
<p>
さらには、\(\sum_{i=1}^nx_i = k+n\) の正の整数解の個数が \(\repecombi{n}{k}\) である。例えば、例えば、\(n=4, k=2\) であれば \(\repecombi{4}{2} = \binom{4+2-1}{2} = \binom{5}{2} = 10\) である。</p>

<h3>2.2. 組み合わせ \(k\)-subset of \(n\)</h3>
<p>
組み合わせは、日本の初等教育では \(\combi{n}{k}\) のように表され、これは二項係数 \(\binom{n}{k}\) に等しい。
\[
\combi{n}{k} = \dbinom{n}{k}
\]
例えば、\(n=4, k=2\) であれば \(\binom{4}{2} = 6\) である。
例えば、\(n=3, k=3\) であれば \(\binom{3}{3} = 1\) である。
</p>
<p>
また、\(k\) 個を区別のある \(n\) 個以下の組に高々１個ずつ分ける場合の数を表している。\(k\le n\) でなければ \(0\) である。
</p>
<h4>二項係数の階乗表示</h4>
<p>
\[
\dbinom{n}{k} = \frac{n!}{k!(n-k)!}
\]
であるので、以下のように表せる。
\[
\dbinom{n}{k} = \frac1{k!}n^{\underline{k}} = \frac1{k!}\permu{n}{k}
\]
</p>

<h3>2.3. 区別のないモノの区別のある組み分け composition of \(n\) with \(k\) terms</h3>
<p>
\(n\) 個を区別のある \(k\) 個の組に分ける場合の数は \(\combi{n-1}{n-k}\) に等しい。但し、\(k\le n\) でなければ \(0\) である。
\[
\combi{n-1}{n-k} = \dbinom{n-1}{n-k}
\]
例えば、\(n=4, k=2\) であれば \(\binom{4-1}{4-2} = 3\) である。また、二項係数の性質
\(
\binom{n}{k} = \binom{n}{n-k}
\)
であることから、以下も成り立つ。
\[
\dbinom{n-1}{n-k} = \dbinom{n-1}{k-1}
\]
例えば、\(n=4, k=2\) であれば \(\binom{4-1}{2-1} = 3\) である。
例えば、\(n=3, k=3\) であれば \(\binom{3-1}{3-3} = \binom{3-1}{3-1} = 1\) である。
</p>
<p>
これは、一列に並べた \(n\) 個の隙間 \(n-1\) 個から \(k-1\) 個選んで仕切りを入れる場合の数と等しい。
</p>

<h3>3.1. ベル数 partition of \(n\) into \(\le k\) subsets</h3>
<p>
\(n\) 人を区別のない \(k\) 個以下の組に分ける場合の数は第２種スターリング数 \(\stirlii{n}{i}\) の総和、つまりベル数 \(B(n, k)\) で表せる。但し、\(k\le n\) でなければ \(k=n\) と等しい。
\[
B(n, k) = \sum_{i=1}^{k}\dstirlii{n}{i}
\]
例えば、\(n=4, k=2\) であれば \(\stirlii{4}{1} + \stirlii{4}{2} = 1 + 7 = 8\) である。
例えば、\(n=3, k=3\) であれば \(\stirlii{3}{1} + \stirlii{3}{2} + \stirlii{3}{3} = 1 + 3 + 1 = 5\) である。
例えば、\(n=2, k=4\) であれば \(\stirlii{2}{1} + \stirlii{2}{2} + \stirlii{2}{3} + \stirlii{2}{4} = 1 + 1 + 0 + 0 = 2\) である。
</p>

<h3>3.2. partition of \(n\) into \(\le k\) elements</h3>
<p>
\(n\) 人を区別のない \(k\) 個以下の組に高々１人ずつ分ける場合の数は以下のように表せる。
\[\small
\begin{cases}
1&n \le k\\
0&\text{otherwise}\\
\end{cases}
\]
</p>

<h3>3.3. スターリング数 partition of \(n\) into \(k\) subsets</h3>
<p>
\(n\) 人を区別のない \(k\) 個の組に分ける場合の数は第２種スターリング数 \(\stirlii{n}{i}\) で表せる。但し、\(k\le n\) でなければ \(0\) である。
\[
\dstirlii{n}{k}
\]
例えば、\(n=4, k=2\) であれば \(\stirlii{4}{2} = 7\) である。
例えば、\(n=3, k=3\) であれば \(\stirlii{3}{3} = 1\) である。
</p>

<h3>4.1. partition of \(n\) into \(\le k\) parts</h3>
<p>
\(n\) 個を区別のない \(k\) 個以下の組に分ける場合の数は一般には表せない。
これは数論の未解決問題のひとつである。
</p>

<h3>4.2. partition of \(n\) into \(\le k\) parts at most one</h3>
<p>
\(n\) 個を区別のない \(k\) 個以下の組に高々１個ずつ分ける場合の数は以下のように表せる。
\[\small
\begin{cases}
1&n \le k\\
0&\text{otherwise}\\
\end{cases}
\]
</p>

<h3>4.3. partition of \(n\) into \(k\) parts</h3>
<p>
\(n\) 個を区別のない \(k\) 個の組に分ける場合の数は一般には表せない。
これは数論の未解決問題のひとつである。
</p>

<h3>4.4. composition of \(n\) with \(k=n\) terms, partition of \(n\) into \(k=n\) subsets or parts</h3>
<p>
\(n\) 人を区別のない \(k\) 個の組に１人ずつ分ける場合の数、\(n\) 個を区別のある、または、ない \(k\) 個の組に１個ずつ分ける場合の数は、以下で表される。
\[\small
\begin{cases}
1&n = k\\
0&\text{otherwise}\\
\end{cases}
\]
</p>

twelvefold_way