- #1
AXidenT
- 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!