Is this equation correct?

73 Views Asked by At

I have a graph with n nodes on left side and m nodes on right side. So for example, in the below picture, I have n=3 and m=4.

enter image description here

Now, I have come up with an equation to find all possible matches. The only condition for the match is, it should just have distinctive edges (or in other words, if there is an edge between n1 -> m1 there can be no other edge as n1 -> m2 or n2 -> m1).

The equation that I framed is,

enter image description here

So for the above picture, the total possible matches can be 36. Is my framed equation correct?

1

There are 1 best solutions below

7
On BEST ANSWER

Your equation is not correct (and does not result in 36 for $n=3, m=4$, but in 48).

Try the equation $\sum_{i=1}^ni!{n\choose i}{m\choose i}$ (for $n\leq m$).

The $i$-th term in the sum represents the number of matches with $i$ edges: each choice of $i$ vertices from the $n$'s combines with each choice of $i$ vertices from the $m$'s and then there are $i!$ different ways to form a valid match. (This formula does not allow a match with no edges).