1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Derangements of 1-Factors Question

  1. Sep 19, 2013 #1
    1. The problem statement, all variables and given/known data

    "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?

    2. Relevant equations

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

    3. 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[itex]\cap[/itex]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!
  2. jcsd
  3. Sep 19, 2013 #2


    User Avatar
    Science Advisor
    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.
  4. Sep 19, 2013 #3
    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
  5. Sep 20, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That looks right. Have you checked it with some simple cases?
  6. Sep 20, 2013 #5
    I just checked with n=2 and 3 and it seemed to work for me. Thank you! :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted