# Derangements of 1-Factors Question

## Homework Statement

"Let i be a fixed interger where 1≤i≤n-2. Given the graph Kn,n write down a formula for the number of ways you can choose a pair of distinct 1-factors which intersect in precisely i edges? Hint: fix one of the 1-factors, choose the i edges which will be common to both and then use derangements to choose the other n-i edges. Now how many ways can you choose the first 1-factor and when are you doubling counting?

## Homework Equations

!n = n! nƩr=0 (-1)r/r!

## The Attempt at a Solution

Following the hint, should I approach it by setting a 1 factor of A = {e1, e2, e3... en} And then set the intersection of A and the other 1-factor B as A$\cap$B = {e1, e2..... ei}

Problem is I don't know how to relate that idea to the formula we've been using - like what values to use for n and r? I would think n=(n-i), but that doesn't seem right. Am I completely off? Really having trouble with this one. :/ Thanks for any help!

haruspex
Homework Helper
Gold Member
You want the remaining n-i edges of B all to mismatch the remaining n-i of A. If these n-i edges of A are the vertex pairs (u1, v1), (u2, v2) ... then you can form the edges for B by permuting the vi so that none of them stay the same. Sounds like a derangement to me.

Thank you for the reply! Could I calculate it like this?:

Number of Possible Matching for Kn,n * Number of intersecting edges in that matching * derangement of the remaining edges * 1/2 (to account for double counting from the first bit)

Where I think that would result in something like:

0.5 * n! * nCi * (n-i)! * n-iƩr=0 (-1)r/r!

It makes sense to me but I don't feel confident about how it relates to the sets. :S

haruspex
Homework Helper
Gold Member
Thank you for the reply! Could I calculate it like this?:

Number of Possible Matching for Kn,n * Number of intersecting edges in that matching * derangement of the remaining edges * 1/2 (to account for double counting from the first bit)

Where I think that would result in something like:

0.5 * n! * nCi * (n-i)! * n-iƩr=0 (-1)r/r!

It makes sense to me but I don't feel confident about how it relates to the sets. :S

That looks right. Have you checked it with some simple cases?

I just checked with n=2 and 3 and it seemed to work for me. Thank you! :D