Beds and Desks

At Euler University, each of the $n$ students (numbered from 1 to $n$) occupies a bed in the dormitory and uses a desk in the classroom.
Some of the beds are in private rooms which a student occupies alone, while the others are in double rooms occupied by two students as roommates. Similarly, each desk is either a single desk for the sole use of one student, or a twin desk at which two students sit together as desk partners.
We represent the bed and desk sharing arrangements each by a list of pairs of student numbers. For example, with $n=4$, if $(2,3)$ represents the bed pairing and $(1,3)(2,4)$ the desk pairing, then students 2 and 3 are roommates while 1 and 4 have single rooms, and students 1 and 3 are desk partners, as are students 2 and 4.
The new chancellor of the university decides to change the organisation of beds and desks: a permutation $\sigma$ of the numbers $1,2,\ldots,n$ will be chosen, and each student $k$ will be given both the bed and the desk formerly occupied by student number $\sigma(k)$.
The students agree to this change, under the conditions that:

Any two students currently sharing a room will still be roommates.
Any two students currently sharing a desk will still be desk partners.

In the example above, there are only two ways to satisfy these conditions: either take no action ($\sigma$ is the identity permutation), or reverse the order of the students.
With $n=6$, for the bed pairing $(1,2)(3,4)(5,6)$ and the desk pairing $(3,6)(4,5)$, there are 8 permutations which satisfy the conditions. One example is the mapping $(1, 2, 3, 4, 5, 6) \mapsto (1, 2, 5, 6, 3, 4)$.
With $n=36$, if we have bed pairing:
$(2,13)(4,30)(5,27)(6,16)(10,18)(12,35)(14,19)(15,20)(17,26)(21,32)(22,33)(24,34)(25,28)$
and desk pairing
$(1,35)(2,22)(3,36)(4,28)(5,25)(7,18)(9,23)(13,19)(14,33)(15,34)(20,24)(26,29)(27,30)$
then among the $36!$ possible permutations (including the identity permutation), 663552 of them satisfy the conditions stipulated by the students.
The downloadable text files beds.txt and desks.txt contain pairings for $n=500$. Each pairing is written on its own line, with the student numbers of the two roommates (or desk partners) separated with a comma. For example, the desk pairing in the $n=4$ example above would be represented in this file format as:

1,3
2,4

With these pairings, find the number of permutations that satisfy the students’ conditions. Give your answer modulo $999\,999\,937$.

This problem is an application of the Burnsides lemma from group theory, particularly in permutation groups. We’ll consider the permutation group of the possible mappings of students.

Firstly, we consider the pairings as cycles in the permutation group. For example the pair (2, 13) can be written as a cycle (2 13). Disjoint cycles commute and thus can be separated. This means that a configuration where students 2 and 13 are roommates can be treated independently from a configuration where students 4 and 30 are roommates and so on.

Then we need to calculate the number of ways of assigning the students such that 2 and 13 are still roommates after a permutation. This is equivalent to the number of orbits in the permutation group that leaves the cycle (2 13) invariant.

Since all our cycles are of length 2, there are two possible orbits for each cycle (2n and vice versa). For all the orbits to be invariant, each cycle must contain the same number of students who use both kind of beds (single and double) and desks (single and twin).

The inclusion of the two options for transposition and the commutability of disjoint cycles, causes every configuration of roommates and desk partners to be multiplied by 2 to the power of the number of cycles.

Next, you take the product of all cycle counts. To find the count of a cycle, you use the formula:
Cycle Count = (((Students in cycle)! / (2 * Number of equivalent cycles that result in same dorm and desk conditions))

After getting the cycle count for all cycles, you multiply them. This is because each cycle can be arranged independently from each other.

Finally, the pairings of beds and desks are independent of each other. Thus, you multiply the count calculated for the beds by the count calculated for the desks to get the total number of permutations that satisfy your conditions.

As the number can be very large, you find the modulo with respect to 999,999,937. This is done to make sure that the answer doesn’t overflow common data types or isn’t too large to manage. A common practice in combinatorics and number theory challenges.

Understand that this is a very complex problem that requires knowledge of advanced mathematics, particularly group theory and combinatorics. And the implementation of this solution would require programming knowledge to handle the large inputs and perform the computations.

Now for the actual problem with n=500, you would have to write a script to read the data from the given files, do the above operations on the data, and then output the number of permutations mod 999,999,937.

More Answers: