Derangements of 1-Factors Question

[AXidenT]

Homework Statement

"Let i be a fixed interger where 1≤i≤n-2. Given the graph K_n,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! ⁿƩ_r=0 (-1)^r/r!

The Attempt at a Solution

Following the hint, should I approach it by setting a 1 factor of A = {e₁, e₂, e₃... e_n} And then set the intersection of A and the other 1-factor B as A\capB = {e₁, e₂... e_i}

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]

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.

 

[AXidenT]

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]

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?

 

[AXidenT]

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