For \(k \le n\), the set of restrictions of \(\mathrm{Fin}\, n\) leaving exactly \(k\) variables free has cardinality \(\binom {n}{k}\, 2^{\, n-k}\), i.e. it equals \(\mathrm{numSRestrictions}\, n\, k\).

For a function \(f\) and parameters \(d, k\), the number of size-\(k\) restrictions \(\rho \) with \(\mathrm{dtDepth}(f|_\rho ) \gt d\) equals the number of restrictions that are \(k\)-restrictions and are bad for \(f\) at depth \(d\) in the counting switching-lemma sense.

For a width-\(w\) DNF \(f\) with no repeated variables per term, \(0 \lt n\), and \(5k \le n\), the probability over uniform size-\(k\) restrictions that the restricted function has decision-tree depth exceeding \(d\) is at most \(\left(10kw/n\right)^d\).

For a width-\(w\) DNF \(f\) with \(0 \lt w\), \(0 \lt n\), and \(k \le n\), the size-\(k\) restriction probability that \(\mathrm{dtDepth}(f|_\rho ) \gt d\) is at most \(\left(10kw/n\right)^d\). This removes the \(5k \le n\) restriction by using the trivial bound when \(5k \gt n\).

The same fixed-size bound written in the form expected by the Bernoulli restriction-cost theorem: the probability is at most \(\left(5k\cdot (2w)/n\right)^d\), using \(10kw/n = 5k\cdot (2w)/n\).