Solution
= Solution
For a binary function class $\mathcal F$, the <shattering coefficient> is
$$
s(\mathcal F,n)=\max_{x_1,\ldots,x_n}
\left|\{(f(x_1),\ldots,f(x_n)):f\in\mathcal F\}\right|.
$$
Its <VC dimension> is the largest $n$ for which $s(\mathcal F,n)=2^n$, with value infinity if there is no largest such $n$. The <Sauer-Shelah lemma> states that, when $\operatorname{VC}(\mathcal F)=d<\infty$,
$$
\boxed{s(\mathcal F,n)\leq\sum_{j=0}^{d}\binom nj.}
$$