How do I find the size of this set? For homework, I need to show that the size of a certain set is $\le 2^{(3n)^k}$ but I'm not getting this (I think I may just misunderstand how the set is defined).
So the set is defined as follows:
You have a boolean domain $\{0,1\}^n$. and $p_1, p_2,\dots,p_n$ boolean variables. You have literals which are $p_i$ or $\neg p_i$, its negation. You use that to construct a 'monomial' which is just a bunch of $p_i$'s or their negations ANDed together. We want to find the size of the class $D_{n,k}$ which contains all disjunctions of the monomials of size AT MOST $k$.
I think I understand what the size of all possible monomials are: $(2n)^k+(2n)^{k-1}+\ldots+(2n)^1$. Does that sound right? If so, is there a way to compress that?
For the second part, I'm a little confused about how the class is defined. Does it mean all monomials have to be present in each element of $D_{n,k}$ and we're counting different orderings of the monomials as different elements of $D_{n,k}$? Or does it mean each element in $D_{n,k}$ is unique because it has a unique subset of all of the monomials but the order of the disjunctions doesn't matter. First, I wanted to clear that up, but even knowing that, I'm still not sure at all where to start on this second part.
 A: To form a monomial from the $n$ Boolean variables, you must decide for each of the $n$ variables whether to use it, its negation, or neither. That’s a $3$-way choice made $n$ times, so there are $3^n$ ways to build a monomial. However, that figure includes monomials of all lengths, not just those of length at most $k$.
Suppose that $0\le i\le k$. To build a monomial of length $i$, you must first choose $i$ of the $n$ variables; you can do this in $\binom{n}i$ ways. For each of those $i$ variables you must then decide whether to use it or its negation; that’s a $2$-way choice made $i$ times, so it can be carried out in $2^i$ ways. Thus, there are $\binom{n}i2^i$ monomials of length $i$, and the total number of distinct monomials of length at most $k$ is
$$\sum_{i=0}^k\binom{n}i2^i\;.\tag{1}$$
Let $M_{n,k}$ be the set of all monomials of length at most $k$. $D_{n,k}$ is the set of all disjunctions of distinct members of $M_{n,k}$. To form such a disjunction, you simply pick a subset of $M_{n,k}$ and take the disjunction of those monomials. $M$ has $2^{|M|}$ subsets, so the problem is asking you to show that
$$2^{|M|}\le 2^{(3n)^k}$$
or, equivalently, that $|M|\le(3n)^k$. In view of $(1)$, that in turn amounts to showing that
$$\sum_{i=0}^k\binom{n}i2^i\le(3n)^k$$
for $0\le k\le n$, which can be done by induction on $n$.
