Understanding growth function of closed intervals in $\mathbb{R}$ I as studying VCdimensions and growth functions and found the following example on Wikipedia:
The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of form $\{c \in [x_1, x_2] | x \in \mathbb{R}\}$ for some $x_{0, 1} \in \mathbb{R}$.
For any set C of m real numbers, the intersection $H \cap C$ contains all runs of between 0 and m consecutive elements of C. The number of such runs of ${m+1 \choose 2} + 1$, so Growth(H, m) = ${m+1 \choose 2} + 1$.
Can anyone please explain to me what does the term &quot;all runs of between 0 and m&quot; refer to here and why the growth function is ${m+1 \choose 2} + 1$ and not ${m+1 \choose 2}$?
Thank you very much!
Let the real numbers be $r_1 &lt; \cdots &lt; r_m$. The intersection $H \cap C$ could be of the form $\{r_i,\ldots,r_j\}$ for $1 \leq i \leq j \leq m$, or empty. There are $\binom{m+1}{2}$ of the first type, and $1$ of the second type.
For example, if $m = 1$ then the possible intersections are
$$ \emptyset, \{r_1\}, $$
if $m = 2$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_1,r_2\}, $$
and if $m = 3$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_3\}, \{r_1,r_2\}, \{r_2,r_3\}, \{r_1,r_2,r_3\}. $$