graph combinatorics: how many graphs are there given k stable sets Let $V_1,\dots, V_k$ be $k$ pairwise disjoint sets and set $V:=\cup_i V_i$. How many graphs $G=(V,E)$ are there such that $\vert e\cap V_i \vert \leq 1$ for all $i\in [k]$, i.e. the $V_i$ are stable sets?
I started with the following argument: 
Let $n_i:= \vert V_i \vert, N:= \sum_i n_i$. The vertices in $V_1$ have $(N-n_1)$ possible vertices to form an edge and there are $n_1$ of them. Next, the vertices in $V_2$ cannot connect to themselves and not to the already counted ones, i.e. $V_1$, and there are $n_2$ of them. This argument can be continued and all those factors need to be multiplied since all can be possibly combined. Thus one would get for the total number:
$$\prod_{j=1}^k n_j \;\left(N - \sum_{i=1}^j n_i \right)$$
Now, I think there is a mistake in my reasoning, because the result looks very strange for a combinatorial argument. 
What did I do wrong?
 A: Your approach is great, but there are some things to fix. First, let's make things easier by counting edges twice. Second, if there are $|E|$ possible edges, the number of possible graphs is $2^{|E|}$ (you have no additional conditions like connectedness, etc.).
So, as you have calculated, there would be $n_i (N-n_i)$ outgoing edges from set $V_i$. Now we could sum all of them up and divide by two, that is:
$$|E| = \frac{1}{2}\sum_i n_i(N-n_i) = \frac{1}{2}(N^2-\sum_in_i^2)$$
which hints on yet another way of calculating edges: you take all of them
$\frac{N(N-1)}{2}$ and remove a clique corresponding to every $V_i$, that is $\frac{n_i(n_i-1)}{2}$ (this neat, because you don't have to deal with possibilities of "halves" of edges). Of course, we could count loops too (the $V_i$s form a partition of $V$, so every loop would be added and removed exactly once), so it is exactly the same as $\frac{N^2}{2}-\sum_i\frac{n_i^2}{2}$, the expression we obtained before. Finally, with $|E|$ possible edges, there are $2^{|E|}$ possible graphs.
Can you take it form here?
