順序付けされていないペアの数 $\{A,B\}$ 与えられた条件下でサブセットの数は可能ですか？
しましょう $S=\{1,2,\ldots,n\}$。順序付けられていないペアの数を見つける$\{A,B\}$ のサブセットの $S$ それをusch $A$ そして $B$ 互いに素である、ここで $A$ そして $B$ または両方が空の場合があります。
ここでのこの質問[1]は、同様の種類の問題を追加しますが、空集合は考慮されていません。
私のアプローチ：
サブセットを選択しましょう $A$ 最初に、サブセットの選択を意味します $B$ に依存します $A$。
しましょう $n(A)$ サブセット内の要素の数を示します $A$。仮定します$n(A)=k$、次にサブセット $B$ 残りの選択を制御できます $(n-k)$ そのような可能なペアの数を意味する要素 $=\binom{n}{k}2^{n-k}$
$$\therefore \text {Total unordered pairs} =\sum_{k=0}^{n}\binom{n}{k}2^{n-k}=\sum_{k=0}^{n}\binom{n}{n-k}2^{n-k}$$ $$=(1+2)^n=3^n$$
ソリューションを確認したいだけです。だから私の解決策に間違いがないかチェックして、提案をしてください。
ありがとう
訂正：これらは、両方のセットの空のケースを含むORDEREDペアの総数です。回答でPhicarが述べているように、順序付けされていないペアでも両方のセットを空の場合に保つために、前に除外して後で追加することができます。したがって、順序付けされていないペアの総数は次のようになります。$\dfrac{3^n-1}{2}+1$。
回答
注意してください、あなたは「サブセットを選択しましょう」と言って注文を受けています $A$"。
たとえば、$n=1$ あなたは数えています $3.$ 主に： $(\{1\},\emptyset),(\emptyset,\{1\}),(\emptyset,\emptyset).$だからあなたは注文を出す必要があります。単に除算することはできないことに注意してください$2$ケースの1つは、空のセットが2回あるためです。だからそれを取り出して、$2$ 後で追加します。 $$\frac{3^n-1}{2}+1.$$
どんな場合でも $x \in S$、3つの可能性があります。
- $x \in A$、 だが $x \not\in B$
- $x \in B$、 だが $x \not\in A$
- $x \not\in A$ そして $x \not\in B$
これは与える $3^n$ の互いに素なサブセットの順序対$S$。順序付けられていないペアを取得するには、次の場合を処理する必要があります。$A=B=\emptyset$ 場合とは異なり $A \neq B$。
したがって、結果として得られる順序付けられていないペアの数は次のようになります。 $\frac{3^n-1}{2}+1$。