Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.