I have a mental block in fully understanding the following notion. Let $G$ be a graph of order $n$ and $H$ a fixed small graph of order $k \le n$. Suppose that there are $d$ copies of $H$ as an induced subgraph of $G.$
Let $d_H(G) = d{n \choose k}^{-1}.$
So, basically, this should be the probability that a randomly chosen $k$-subset of vertices of $G$ induce a copy of $H.$ Now in order to compute $d_H(G)$ one can iterate over all graphs of order $k \le \ell \le n$ in the following way
$$d_H(G) =\sum_{|V(I)|= \ell} d_I(G) d_H(I).$$
Which is where I get a bit confused. I don't seem to fully understand the formula since I don't see why we don't overcount some occurrences of $H$? How would that identity follow from the probabilistic interpretation of $d_H(G)?$ I would assume one could use the law of total probability but I don't see why would the events that a specific $k$-set induce $H$ be independent.
Can someone provide a clearer interpretation/explanation of $(1)$?
Consider the following operation: We first choose a set $T$ of $\ell$ vertices of $H$ uniformly at random. We then choose a $k$ vertex subset $S$ of $T$ uniformly at random. If we ignore $T$ entirely, the resulting distribution on $S$ is uniform. In particular, the probability that the vertices of $S$ induce $G$ is $d_G(H)$. On the other hand, we can use the law of total probability to write $$\mathbf{P}(S \textrm{ induces } G) = \sum_{I} \mathbf{P}(S \textrm{ induces } G \vert T \textrm{ induces } I) \mathbf{P}(T \textrm{ induces } I)$$ The first term in the product corresponds to $d_I(G)$, while the second corresponds to $d_H(I)$.
I don't need any independence when I do this, other than that $S$ is uniform over all $k$-subsets of $T$ regardless of what $T$ is.