In §2.2.1 of Introduction To Machine Learning: An Early Draft Of A Proposed Textbook, author Nilsson says about conjunctions of Boolean literals:
It is easy to show that there are exactly $3^n$ possible terms of $n$ variables. The number of terms of size $k$ or less is bounded from above by $\sum^k_{i=0}C(2n,i)=O(n^k)$, where $C(i,j)=\dfrac{i!}{(i-j)!j!}$ is the binomial coefficient.
I understand these parts:
The number of terms of size $k$ or less is $\sum^k_{i=0}C(2n,i)$, where $C(i,j)=\dfrac{i!}{(i-j)!j!}$ is the binomial coefficient.
The number of terms of size $k$ or less is given by the sum, for $i$ in $0$ to $k$, of combinations of $n$ variables (times 2 for complemented and uncomplemented forms) taken $i$ at a time.
My questions are:
- Why are there $3^n$ possible terms of $n$ variables?
- Why is the sum of combinations of terms of different length equal to $O(n^k)$?
- Why is it an upper bound and not an exact count? Is it because the formula doesn't prevent uncomplemented and complemented variables appearing together?
Each variable $x_i$ either appears as is, appears as its negative, or does not appear. I infer from context that even an expression with variables absent is still counted as a term with $n$ variables, though its size is less than $n$.
Since $$C(n,k)=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots (n-k+1)}{k!}\le\frac{n\cdot n\cdots n}{k!}\le n^k,$$so in particular $C(2n,i)\le (2n)^i$, we have $$\sum_{i=0}^{k}C(2n,i)\le \sum_{i=0}^k (2n)^i=\frac{(2n)^{k+1}-1}{2n-1}\le \frac{(2n)^{k+1}}{2n-1}=(2n)^k\cdot \frac1{1-\frac1{2n}}$$Viewing $k$ as a constant, this is $O(n^k)$ as $n\to\infty$. The second inequality is the finite geometric series formula. Note that the $\frac1{1-\frac1{2n}}$ approaches $1$ in the limit, so it can be ignored. Concretely, since $n\ge 1$, $\frac1{1-\frac1{2n}}\le 2$.
It is exactly because of what you said in your second sentence.