Derangements of 1-Factors Question

  • Thread starter AXidenT
  • Start date
In summary, you can solve this problem by trying to find a derangement that will result in the number of matching edges being the same as the number of intersecting edges.
  • #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!
 
Physics news on Phys.org
  • #2
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
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
AXidenT said:
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
I just checked with n=2 and 3 and it seemed to work for me. Thank you! :D
 

1. What are derangements of 1-factors?

Derangements of 1-factors refer to a type of mathematical problem where a set of elements is rearranged in such a way that none of the elements are in their original position. In other words, it is a permutation where no element is in its original position.

2. What is the formula for calculating derangements of 1-factors?

The formula for calculating derangements of 1-factors is n!/e, where n is the number of elements and e is the mathematical constant 2.71828... (Euler's number).

3. How do derangements of 1-factors differ from other types of permutations?

Derangements of 1-factors differ from other types of permutations in that they do not allow any element to remain in its original position. In other types of permutations, there may be some elements that remain in their original position.

4. What is the significance of derangements of 1-factors in real-world applications?

Derangements of 1-factors have applications in many fields, including computer science, statistics, and cryptography. They are used to calculate the probability of certain events and to generate random permutations.

5. Can derangements of 1-factors be applied to larger sets of elements?

Yes, derangements of 1-factors can be applied to sets with any number of elements. However, as the number of elements increases, the number of possible derangements also increases, making the calculations more complex.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
546
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
Replies
6
Views
310
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
975
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
Back
Top