A385919 Number of non-isomorphic round-robin tournament schedules for 2*n players, where the order of rounds does not matter.

1, 1, 6, 6930, 12257280, 526915620, 1132835421602062347

Offset: 1

Author

Peter Boonstra and Hilko Koning, Jul 25 2025

Keywords

• nonn
• more

Comments

A round-robin tournament schedule with 2*n players consists of 2*n-1 rounds, where in each round the players are divided into n disjoint pairs, and every player plays against every other player exactly once.

Also the number of non-isomorphic 1-factorizations of the complete graph K_{2n}. We count 1-factorizations of the complete graph K_{2n} up to isomorphism, where 'isomorphism' means that two factorizations are considered the same if one can be transformed into the other by:

(1) relabeling the vertices (i.e., permuting the players), and

(2) reordering the rounds (i.e., permuting the 1-factors).

This is equivalent to counting round-robin tournament schedules where players are unlabeled and the order of the rounds is irrelevant.

Number of ways to partition the edge set of K_{2n} into 2n-1 perfect matchings (1-factors), up to isomorphism. Also the number of non-isomorphic 1-factorizations of the complete graph K_{2n}.

Examples

			a(1) = 1: one match between two players.
a(2) = 1: three matches (A-B, C-D, etc) organized into three rounds. All factorizations are isomorphic.
a(3) = 6: The 15 edges of K_6 can be partitioned into 5 rounds of 3 matches in 6 non-isomorphic ways.
		

References

• Colbourn and Dinitz, CRC Handbook of Combinatorial Designs, 2nd ed. (2006), entry on 1 factorizations of complete graphs.

Links

• Petteri Kaski and Patric R. J. Östergård, There are 1132835421602062347 nonisomorphic one-factorizations of K_14, arXiv:0801.0202 [math.CO], 2007.
• Hilko Koning, Non-isomorphic 1-factorizations of K_6 (6 labeled players, 5 rounds each).
• Brendan D. McKay and Ian M. Wanless, There are 526915620 nonisomorphic one-factorizations of K_12.
• Wikipedia, 1-factorization.
• R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium 15 (1976), pp. 647-659.

Crossrefs

Cf. A000085 (number of involutive permutations), A000569 (number of 1-factorizations of K_{2n}, not up to isomorphism).

Programs

Mathematica

(* n=4 is extremely memory- and CPU-intensive. The Mathematica approach is theoretically correct but utterly infeasible for n >= 4 *)
ClearAll[nonIsomorphic1Factorizations];
nonIsomorphic1Factorizations[n_Integer?Positive] :=
  Module[{vertices = Range[2 n], edges, matchings, factorizations,
    perms, canonical, relabel, isIsomorphicQ, nonIsomorphicList = {}},
    edges = Subsets[vertices, {2}];
   matchings =
    Select[Subsets[edges, {n}], DuplicateFreeQ[Flatten[#]] &];
   factorizations =
    Select[Subsets[matchings, {2 n - 1}], DuplicateFreeQ[Join @@ #] &];
   canonical[fact_] := Sort[Sort /@ fact];
   perms = Permutations[vertices];
   relabel[fact_, perm_] :=
    Sort[Sort /@ (Sort /@
          Replace[#, {a_, b_} :>
            Sort[{perm[[a]], perm[[b]]}], {2}] & /@ fact)];
   isIsomorphicQ[f1_, f2_] :=
    MemberQ[relabel[f1, #] & /@ perms, canonical[f2]];
   Do[If[NoneTrue[nonIsomorphicList, isIsomorphicQ[fact, #] &],
     AppendTo[nonIsomorphicList, fact]], {fact, factorizations}];
   nonIsomorphicList];
(*Display the number of non-isomorphic 1-factorizations for K_{2n} for n=1 to 5*)
Table[With[{list = nonIsomorphic1Factorizations[n]},
  Print["n = ", n, " \[RightArrow] ", Length[list],
   " non-isomorphic 1-factorizations of K_", 2 n];
  Length[list]], {n, 1, 5}]