Three-State Subset Count with Bold Elements

Combinatorics · Easy · Free problem
Erica is constructing a subset $S$ of $[n] = \{1, 2, \ldots, n\}$. For any element $x \in [n]$, she has three options: - Exclude $x$ from $S$ - Include $x$ in $S$ (confident) - Include $x$ in $S$ but boldface it (uncertain) An element may appear at most once in $S$, so the set $\{1, 2, \mathbf{2}, 4\}$ is invalid. For example, $\{1, 2\}$, $\{1, \mathbf{3}, 4\}$, and $\{\mathbf{1}, \mathbf{2}, \mathbf{3}, \mathbf{4}\}$ are all valid. How many valid subsets $S$ can Erica construct when $n = 5$?

Open the full interactive solver, hints, and worked solution →