部分集合の半順序とか - イガブロギュ

半順序について考えていて、次のような問題を思い付きました。
要素数が n の有限集合 A(つまり |A|=n) の部分集合全体を P(A) で表すとき、 $x, y \in P(A)$ で $x \subset y$ となるような組 $\langle x, y \rangle$ は何通りあるか。
ただし、今は $x \sub y$ は、x が y の真部分集合であるという意味です。
では、解いてみましょう。
$x \in P(A)$ かつ $|x|=i$ とします。
このとき、 $y \in P(A)$ かつ $|y| = i+j$ かつ $x \subset y$ となるような y は、A の n 個の要素のうち x の i 個の要素を除いた n-i 個から j 個の要素を選べば作れるので ${}_{n-i}\mathrm{C}_{j}$ 通り。
よって、 $x \subset y$ となる y の総数は
$\sum_{j=1}^{n-i} {}_{n-i}\mathrm{C}_{j} = \sum_{j=0}^{n-i} {}_{n-i}\mathrm{C}_{j} - {}_{n-i}\mathrm{C}_{0} = 2^{n-i}-1$ 通り。
ところで、 $x \in P(A)$ かつ $|x|=i$ となるような x は ${}_n\mathrm{C}_i$ 通り。
以上により、問題の答えは
$\sum_{i=0}^n (2^{n-i}-1) \cdot {}_n\mathrm{C}_i = \sum_{i=0}^n (2^i-1) \cdot {}_n\mathrm{C}_i = \sum_{i=0}^n 2^i \cdot {}_n\mathrm{C}_i + \sum_{i=0}^n {}_n\mathrm{C}_i$ …(*)
ここで、二項定理により
$(a+b)^n = \sum_{i=0}^n {}_n\mathrm{C}_i a^{n-i} b^i$ より $(1+k)^n = \sum_{i=0}^n {}_n\mathrm{C}_i \cdot k^i$
つまり
$\sum_{i=0}^n k^i \cdot {}_n\mathrm{C}_i = (k+1)^n$
これの k に 2 または 1 を代入したものを (*) に代入すると、求める総数は
$3^n - 2^n$
となります。
うわー。びっくり。
式が簡単なことはもとより、3 が不思議です。
ちなみに、k氏に言われて気付いたのですが、真部分集合ではなく単なる部分集合といったときには、部分集合の総数が $2^n$ であることから、求める総数は $3^n$ になります。
どっかの大学の入試問題として既に出題されていそうな問題ですが、なかなか面白い結果を得ることができました。
数学は、自分で問題を見つけて自分で予想を立てて自分で証明をするという一連の流れが楽しいのです。
今回の問題に関連した、答えが $4^n$ になる問題なんかを考えると面白いかも。