A356584 Number of instances of the stable roommates problem of cardinality n (extension to instances of odd cardinality).

1, 1, 2, 60, 66360, 4147236820, 19902009929142960, 10325801406739620796634430, 776107138571279347069904891019268480, 10911068841557131648034491574230872615312437194176

Offset: 1

Author

Zacharie Moughanim, Aug 13 2022

Keywords

• nonn

Comments

At first sight, the number of distinct instances of cardinality n appears to be (n-1)!^n, as an instance may be described as an n X n matrix with the first column fixed, and with each integer between 1 and n appearing once in each line.

However, some distinct instances (with this counting method) only differ by a permutation.

Hence, the establishment of a group action of S_n on A_n, and more specifically the Burnside formula, can be used to count the orbits, so in this specific case the number of instances that are really distinct.

Thus, the sequence gives the number of distinct orbits.

Examples

			For n=3 there are 2 instances: I = {(1,2,3),(2,3,1),(3,1,2)} and J = {(1,2,3),(2,1,3),(3,1,2)}. It is meant to be read: In I, the first agent prefers agent 2 to agent 3, the second agent prefers agent 3 to agent 1, ... And other instances are just one of these two, differing by a permutation.
Example: the instance K = {(1,2,3),(2,1,3),(3,2,1)} is (1 2) * J, so it is not counted as a different instance. (The '*' operation is the group action described above.)
		

Links

• Vladimir Ivanov, Table of n, a(n) for n = 1..31
• Zacharie Moughanim, Proof of the formula
• Wikipedia, Stable Roommates Problem

Crossrefs

Cf. A200472.

Programs

Mathematica

a[n_]:=Sum[((((n-1)!)*k)^k)/((n^k)*k!), {k, Divisors[n]}]; Array[a, 10] (* Stefano Spezia, Aug 14 2022 *)

Formula

In general, there are Sum_{k|n} ((k*((n-1)!))^k)/(k!*n^k) instances of the stable roommates problem.

a(n) = (1/n!)*Sum_{k|n} (n-1)!^(n/k)*(k-1)!^(n/k) * A200472(n,n/k) = Sum_{k|n} ((k*((n-1)!))^k)/(k!*n^k).