OFFSET
1,3
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.
LINKS
Vladimir Ivanov, Table of n, a(n) for n = 1..31
Zacharie Moughanim, Proof of the formula
Wikipedia, Stable Roommates Problem
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).
EXAMPLE
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.)
MATHEMATICA
a[n_]:=Sum[((((n-1)!)*k)^k)/((n^k)*k!), {k, Divisors[n]}]; Array[a, 10] (* Stefano Spezia, Aug 14 2022 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Zacharie Moughanim, Aug 13 2022
STATUS
approved