A356584 - OEIS

%I #81 Jan 12 2023 20:12:17

%S 1,1,2,60,66360,4147236820,19902009929142960,

%T 10325801406739620796634430,776107138571279347069904891019268480,

%U 10911068841557131648034491574230872615312437194176

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

%C 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.

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

%C 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.

%C Thus, the sequence gives the number of distinct orbits.

%H Vladimir Ivanov, <a href="/A356584/b356584.txt">Table of n, a(n) for n = 1..31</a>

%H Zacharie Moughanim, <a href="/A356584/a356584_7.pdf">Proof of the formula</a>

%H Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Stable_roommates_problem">Stable Roommates Problem</a>

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

%F 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).

%e 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.

%e 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.)

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

%Y Cf. A200472.

%K nonn

%O 1,3

%A _Zacharie Moughanim_, Aug 13 2022