|
|
A356584
|
|
Number of instances of the stable roommates problem of cardinality n (extension to instances of odd cardinality).
|
|
2
|
|
|
1, 1, 2, 60, 66360, 4147236820, 19902009929142960, 10325801406739620796634430, 776107138571279347069904891019268480, 10911068841557131648034491574230872615312437194176
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|