A365520 Number of 1-factorizations of complete graph K_{2n} that all share one arbitrary pairing in common.

1, 1, 2, 416, 11672064, 266965735243776, 9500592190171594780311552

Offset: 1

Author

Brian Lathrop, Sep 08 2023

Keywords

• nonn
• more

Comments

Consider a round robin tournament with 2n teams competing. For the first round, select a set of pairings arbitrarily. a(n) is the number of possible round robin tournaments after choosing one of those sets of pairings.

a(n) can be obtained by dividing A000438(n) by the product (2n-3)*(2n-5)*...*3*1 when n > 2. For n = 1 or n = 2, a(n) is simply 1, since there is only one way to set up those rounds with 2 or 4 teams.

To show how this works, consider the number of possible round robin tournaments given 8 teams (A000438(4) = 6240) identified by the letters A through H.

Each of these tournaments can be constructed from a set of matchups of this form:

(AB)(XX)(XX)(XX)

(AC)(YY)(YY)(YY)

(AD)(YY)(YY)(YY)

(AE)(YY)(YY)(YY)

(AF)(YY)(YY)(YY)

(AG)(YY)(YY)(YY)

(AH)(YY)(YY)(YY)

Note that the 6240 tournaments can be divided evenly by the number of ways the "X" teams can be paired up to fill the arbitrary round. This is why A001147(3) = 15 is a factor, since there are 5 ways to pick the first pair, followed by 3 ways to pick the second pair.

For larger numbers of teams, there are more ways to pair up; e.g., for 10 teams, there will be a factor of 7*5*3, and for 12 teams, a factor of 9*7*5*3, and so on.

Examples

			For n = 3, given teams A through F (2n), the only two round robin tournaments that share the pairing (AB)(CD)(EF) are:
   (AB)(CD)(EF)
   (AC)(BE)(DF)
   (AD)(BF)(CE)
   (AE)(BD)(CF)
   (AF)(BC)(DE)
and
   (AB)(CD)(EF)
   (AC)(BF)(DE)
   (AD)(BE)(CF)
   (AE)(BC)(DF)
   (AF)(BD)(CE)
which agrees with a(3) = 2.
		

Crossrefs

Cf. A000438, A001147.

Formula

a(n) = A000438(n)/A001147(n-1).