# Tag Info

For the version where every clause must have exactly $k$ literals: There are ${n \choose k} 2^n$ possible clauses. (Why? Because you must choose exactly $k$ of the variables to appear in the clause, and then for each variable, you choose whether it appears negated or not.) A formula is obtained by choosing some subset of those possible clauses. So, the ...