0
$\begingroup$

Consider that we have a complete bipartite graph with $2n $ vertices. In each part of this graph we have $n $ vertices. We want to choose $i\leq n$ edges of this graph such that none of the two selected edges has a common vertex.

How many choices do we have?

For example, when $i=n$, we have $n!$ choices.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There are $\dbinom{n}{i}$ ways to choose $i$ points on one side of the bipartite graph for the edges to begin. After you've chosen these, there are $\frac{n!}{(n-i)!}$ ways to choose the $i$ distinct points on the other side that the edges on the first side connect to. So in total, there are $\dbinom{n}{i}\frac{n!}{(n-i)!}$ ways for this to occur.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .