# 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.

-
Please check to be sure that I interpreted all of the formulas correctly. –  Brian M. Scott Mar 28 '13 at 3:43

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$.

-
Does it make a difference if you choose i of the n variables and then choose whether to use it or its negation, instead of just choosing i of the 2n variables (this already includes negations). This way you can have a variable and its negation in a monomial. –  user1136342 Mar 28 '13 at 4:24
@user1136342: Since a monomial that includes both $p$ and $\neg p$ can always be omitted, I’m reasonably sure that the intention is to choose $i$ of the $n$ and then decide which are to be positive and which negative. –  Brian M. Scott Mar 28 '13 at 4:28