A035481
Number of n X n symmetric matrices whose first row is 1..n and whose rows and columns are all permutations of 1..n.
Original entry on oeis.org
1, 1, 1, 1, 4, 6, 456, 6240, 10936320, 1225566720, 130025295912960, 252282619805368320, 2209617218725251404267520, 98758655816833727741338583040
Offset: 0
a(3) = 1 because after 123 in the first row and column, 213 is not allowed for the second row, so it must be 231 and thus the third row is 312.
-
(* This script is not suitable for n > 6 *) matrices[n_ /; n > 1] := Module[{a, t, vars}, t = Table[Which[i==1, j, j==1, i, j>i, a[i, j], True, a[j, i]], {i, n}, {j, n}]; vars = Select[Flatten[t], !IntegerQ[#]& ] // Union; t /. {Reduce[And @@ (1 <= # <= n & /@ vars) && And @@ Unequal @@@ t, vars, Integers] // ToRules}]; a[0] = a[1] = 1; a[n_] := Length[ matrices[n]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 6}] (* Jean-François Alcover, Jan 04 2016 *)
A000438
Number of 1-factorizations of complete graph K_{2n}.
Original entry on oeis.org
1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040
Offset: 1
- CRC Handbook of Combinatorial Designs (see pages 655, 720-723).
- N. T. Gridgeman, Latin Squares Under Restriction and a Jumboization, J. Rec. Math., 5 (1972), 198-202.
- W. D. Wallis, 1-Factorizations of complete graphs, pp. 593-631 in Jeffrey H. Dinitz and D. R. Stinson, Contemporary Design Theory, Wiley, 1992.
- Jeffrey H. Dinitz, David K. Garnick, and Brendan D. McKay, There are 526,915,620 nonisomorphic one-factorizations of K_{12}, J. Combin. Des. 2 (1994), no. 4, 273-285.
- Alan Hartman, and Alexander Rosa, Cyclic one-factorization of the complete graph, European J. Combin. 6 (1985), no. 1, 45-48.
- Dieter Jungnickel, and Vladimir D. Tonchev, Counting Steiner triple systems with classical parameters and prescribed rank, arXiv:1709.06044 [math.CO], 2017.
- Petteri Kaski, and Patric R. J. Östergård, There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of K14, Journal of Combinatorial Designs 17 (2009) 147-159.
- Mario Krenn, Xuemei Gu, and Anton Zeilinger, Quantum Experiments and Graphs: Multiparty States as coherent superpositions of Perfect Matchings, arXiv:1705.06646 [quant-ph], 2017 and Phys. Rev. Lett. 119, 240403, 2017. [Mario Krenn said in an email, "We would not have discovered this connection between quantum mechanical experiments and graph theory, thus the physical interpretations and all the generalisations we are developing right now, without you and A000438."]
- D. V. Zinoviev, On the number of 1-factorizations of a complete graph [in Russian], Problemy Peredachi Informatsii, 50 (No. 4), 2014, 71-78.
- Index entries for sequences related to tournaments
For K_16 the answer is approximately 1.48 * 10^44 and for K_18 1.52 * 10^63. - Dinitz et al.
a(7) found by Patric Östergård and Petteri Kaski (petteri.kaski(AT)cs.helsinki.fi), Sep 19 2007
A036980
Number of (2n) X (2n) symmetric matrices each of whose rows is a permutation of 1..(2n).
Original entry on oeis.org
1, 2, 96, 328320, 440952422400
Offset: 0
Showing 1-3 of 3 results.
Comments