Solution
= Solution
A set of points $x_1,\ldots,x_n$ is shattered by $H$ when every one of the $2^n$ binary label vectors is realized by some $h\in H$. The <shattering coefficient> is
$$
s(H,n)=\max_{x_1,\ldots,x_n}
\left|\{(h(x_1),\ldots,h(x_n)):h\in H\}\right|,
$$
and the <VC dimension> is
$$
VC(H)=\sup\{n:s(H,n)=2^n\}.
$$
The Sauer--Shelah lemma states that if $VC(H)=D<\infty$, then
$$
s(H,n)\leq\sum_{j=0}^{D}\binom nj
$$
for every $n$; in particular $s(H,n)\leq(n+1)^D$.