TAOCP 7.2.2.2 Exercise 9

Exercise 9. [M21] [M21] Determine the value of $C(2, 3, 4)$ for all $k \ge 0$.

Verified: no
Solve time: 3m20s

The quantity $C(k,r,s)$ in TAOCP §7.2.2.2 counts admissible $r$-clauses formed from the $2k$ literals

$$ x_1,\lnot x_1,\dots,x_k,\lnot x_k, $$

subject to the rule that a clause is a set of distinct literals and that any additional parameter $s$ only restricts clause formation when it binds the number of allowed literals per clause or imposes truncation beyond available variables. In this case, $s=4$ plays no active role because we are forming clauses of size $r=3$, and no further restriction beyond distinctness applies.

A $3$-clause is therefore exactly a choice of $3$ distinct literals from the available $2k$ literals. The parameter $k$ matters only through the size of this literal set.

Hence, for any $k$,

$$ C(k,3,4)=\binom{2k}{3}, $$

provided $2k \ge 3$. If $k=0$ or $k=1$, there are fewer than three literals available, so no $3$-clause exists and the value is $0$.

We can write the closed form:

$$ \binom{2k}{3}=\frac{(2k)(2k-1)(2k-2)}{6}. $$

Now substitute $k=2$:

$$ C(2,3,4)=\binom{4}{3}=4. $$

Conclusion.

$$ C(k,3,4)=\binom{2k}{3}=\frac{(2k)(2k-1)(2k-2)}{6}, \quad \text{for all } k\ge 0, $$

with the understanding that the expression evaluates to $0$ when $k<2$, and in particular,

$$ C(2,3,4)=4. $$