Counting a bipartite graph in two ways

Question

I've got a bipartite graph where the left side corresponds to points $X = \{x_1,\ldots,x_n\}$ and the right side corresponds to subsets $\mathcal F = \{A_1,\ldots,A_m\}$ of $X$. There's an edge between the left and right side if a point is a member of a subset. $d(x)$ is the out-degree of a vertex on the left side of the graph, and indicates the number of members of $\mathcal F$ that contain $x$.

While it's easy to count the bipartite graph in two ways and show:

$$\sum_{A\in \mathcal F}^m\big| A \big| = \sum_{x\in X}d(x)$$

I'm trying to show that:

$$\sum_{i,j=1}^m\big| A_i\cap A_j \big| = \sum_{x\in X}d(x)^2$$

This seems intuitive, but where do I start to get a more rigorous proof?

Answer 1

For the first equation (and title), you're not double counting a graph. You are counting, in two different ways, the number of pairs $(x,A)$ with $x\in X$ and $A\in\mathcal P$ satisfying $x\in A$.

For the second equation, count in two different ways the number of triples $(x,A,B)$ with $x\in X$ and $A,B\in\mathcal P$ satisfying $x\in A\cap B$.

Answer 2

We can view double counting as counting pairs $(x_i,A_j)$ where $x_i\in A_j$. For your proposed extension, I'd count triples $(x_i,A_j,A_k)$ where $x_i\in A_k$ and $x_i\in A_k$.