MathGoldMedalist
Sign InRegister

Toolkit 72

Double Counting (Consider from Different Aspects)

A,B⊆{1,2,…,n}A,B\subseteq\{1,2,\ldots,n\}
A∩B=∅A\cap B=\varnothing

Instead of considering the subsets, we should consider the elements.

Each element has 3 possible choices for AA and BB:

AB✓✓✓××✓\begin{array}{c|c} A & B\\ \hline \checkmark & \checkmark\\ \checkmark & \times\\ \times & \checkmark \end{array}

Therefore,

3⋅3⋅3⋯3⏟n times=3n.\underbrace{3\cdot 3\cdot 3\cdots 3}_{n\text{ times}}=3^n.
Back to Toolkit