login
A365520
Number of 1-factorizations of complete graph K_{2n} that all share one arbitrary pairing in common.
0
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.
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
Sequence in context: A153911 A259562 A177321 * A080392 A154541 A119120
KEYWORD
nonn,more
AUTHOR
Brian Lathrop, Sep 08 2023
STATUS
approved