Derangements of 1-Factors Question

  • Thread starter AXidenT
  • Start date
  • #1
26
2

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[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!
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,578
6,450
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.
 
  • #3
26
2
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
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,578
6,450
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?
 
  • #5
26
2
I just checked with n=2 and 3 and it seemed to work for me. Thank you! :D
 

Related Threads on Derangements of 1-Factors Question

  • Last Post
Replies
3
Views
1K
Replies
1
Views
1K
Replies
4
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
4
Views
710
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
762
  • Last Post
Replies
0
Views
1K
Replies
1
Views
1K
Top