条件「集合の要素数がその集合に属している」
はじめに
鈴木先生の集合と論理の入門書[1]で,あまり見ない面白い問題があったので,その一般化を考えてみる.
問題
$n$を自然数とする$.X=\{1,\dots ,n\} $の部分集合$B$のうち,
\begin{align*}
|B|\in B
\end{align*}
を満たすものは何個あるか.ただし,$|B|$は$B$の要素数を表す.
解答1
$|B|=k\ \ \ (k\in X)$とする.$k\in B$を満たす$B$の個数は,$X\backslash \{k\}$から$k-1$個を取る組み合わせの個数だけあるので, $_{n-1}C_{k-1}$個.
よって求める答えは
\begin{align}
\sum _{k=1}^{n} {_{n-1}C_{k-1}}=2^{n-1}
\end{align}
組み合わせの基本的な問題ですが,あまり高校数学で見かけない問題です.
もう少し一般化してみましょう.
$X$の空でない部分集合$B$に対して,さらに条件を満たす部分集合$C\subset B$の個数を考え,$B$について和を取った値を考えてみましょう.
$n$を自然数とする$.X=\{1,\dots ,n\} $の部分集合$B$に対して,
\begin{align}
\sum _{B\subset X} {|\{C\subset B;|C|\in C\}|}
\end{align}
を求めよ.
解答2
空でない部分集合$C\subset X$のうち,$|C|=k\in X,|C|\in C$を満たすものは$_{n-1}C_{k-1}$個.
この$C$に対して$C\subset B\subset X$を満たす$B$の個数は,$C$に属していない$n-k$個が入るか入らないかを考えればよいので$2^{n-k}$個
よって,
\begin{align}
\sum _{B\subset X} {|\{C\subset B;|C|\in C\}|}&=\sum _{k=1}^n {_{n-1}C_{k-1} 2^{n-k}} \\
&=3^{n-1}
\end{align}
先ほどの値もそうでしたが,二項定理が綺麗に表れて良い問題と言いたくなりますね.
確率を使って問題1を解いてみましょう.
$n$を自然数とする$.X=\{1,\dots ,n\} $の部分集合$B$を取るとき,$|B|\in B$となる確率を求めよ.
解答3
(i)$\displaystyle P(k\in B \ |\ |B|=k)$について,
$|B|=k$の場合の数は$_{n}C_{k}$通り.さらに,$k\in B$となるのは$_{n-1}C_{k-1}$通り.よって
$\displaystyle P(k\in B \ |\ |B|=k)=\frac{_{n-1}C_{k-1}}{_{n}C_{k}}=\frac{k}{n} $.
(ii)$\displaystyle P(|B|=k)$について,$B\subset X$の個数は$2^n$個.そのうち$|B|=k$となるのは$_{n}C_{k}$個なので,
$\displaystyle P(|B|=k)=\frac{_{n}C_{k}}{2^n}$.
よって求める確率は
\begin{align}
P(|B|\in B)&=\sum _{k=1}^n {P(k\in B \ |\ |B|=k)P(|B|=k)}\\
&=\sum _{k=1}^n {\frac{k}{n} \frac{_{n}C_{k}}{2^n}}
=\frac{1}{n\cdot 2^n}\sum _{k=1}^n k {_{n}C_{k}}\\
&=\frac{1}{n\cdot 2^n}\cdot n\cdot 2^{n-1}=\frac{1}{2}
\end{align}
この答えから,期待値を考えることにより問題1の答えが分かります.
もう一個条件を増やしてみましょう.
$n$を自然数とする$.X=\{1,\dots ,n\} $の部分集合$B$のうち,
\begin{align*}
\min B=|B|&\in B
\end{align*}
を満たすものは何個あるか.
解答4
$|B|=k$と置く.$k=\min B$より,$B\subset \{k,\dots ,n\}$.
よって,$B$の個数は$k+1,\dots ,n$の$n-k$個から$k-1$個をとる組み合わせなので$_{n-k}C_{k-1}$.
ただし,$n-k\ge k-1$なので,$k=\lfloor \frac{n+1}{2}\rfloor$.
よって求める個数は,
\begin{align}
\sum_{k=1}^{\lfloor \frac{n+1}{2}\rfloor} {_{n-k}C_{k-1}}=F_{n+1}
\end{align}
ただし,$F_n$は$n$番目のフィボナッチ数.
綺麗.
最後の和は[2]
ProofWiki “Fibonacci Number as Sum of Binomial Coefficients”
より,帰納法によって証明されます.
参考文献
[1]
鈴木 登志雄, 例題で学ぶ集合と論理, 森北出版, 2016
[2]
ProofWiki “Fibonacci Number as Sum of Binomial Coefficients”
