login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Zacharie Moughanim, Proof of the formula
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
Cf. A200472.
Sequence in context: A082787 A078423 A231024 * A121493 A078491 A182856
KEYWORD
nonn
AUTHOR
Zacharie Moughanim, Aug 13 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)