cp's OEIS Frontend

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

%I A356584 #85 Mar 23 2025 18:38:42
%S A356584 1,1,2,60,66360,4147236820,19902009929142960,
%T A356584 10325801406739620796634430,776107138571279347069904891019268480,
%U A356584 10911068841557131648034491574230872615312437194176
%N A356584 Number of instances of the stable roommates problem of cardinality n (extension to instances of odd cardinality).
%C A356584 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 A356584 However, some distinct instances (with this counting method) only differ by a permutation.
%C A356584 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 A356584 Thus, the sequence gives the number of distinct orbits.
%H A356584 Vladimir Ivanov, <a href="/A356584/b356584.txt">Table of n, a(n) for n = 1..31</a>
%H A356584 Zacharie Moughanim, <a href="/A356584/a356584_7.pdf">Proof of the formula</a>
%H A356584 Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Stable_roommates_problem">Stable Roommates Problem</a>
%F A356584 In general, there are Sum_{k|n} ((k*((n-1)!))^k)/(k!*n^k) instances of the stable roommates problem.
%F A356584 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 A356584 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 A356584 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 A356584 a[n_]:=Sum[((((n-1)!)*k)^k)/((n^k)*k!), {k, Divisors[n]}]; Array[a, 10] (* _Stefano Spezia_, Aug 14 2022 *)
%Y A356584 Cf. A200472.
%K A356584 nonn
%O A356584 1,3
%A A356584 _Zacharie Moughanim_, Aug 13 2022