Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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$.

share|improve this answer
    
i thought "double counting" and "counting in two ways" referred to the same technique -- would it be better to update the title and question with "count in two ways"? –  aaronstacy Jan 29 '13 at 15:02
1  
"Double counting" means "counting in two ways". But "double counting graphs" does not mean "double counting pairs $(x,A)$ with $x\in A$". –  Colin McQuillan Jan 29 '13 at 15:43
    
ah, i see. i'll update the question's wording. –  aaronstacy Jan 29 '13 at 17:27

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.