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,3

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.

Links

Table of n, a(n) for n=1..7.

Formula

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

Example

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.

Sequence in context: A153911 A259562 A177321 * A080392 A154541 A119120

Adjacent sequences: A365517 A365518 A365519 * A365521 A365522 A365523

Keyword

nonn,more

Author

Brian Lathrop, Sep 08 2023

Status

approved