A200472 -id:A200472 - cp's OEIS frontend

A038041 Number of ways to partition an n-set into subsets of equal size.

1, 2, 2, 5, 2, 27, 2, 142, 282, 1073, 2, 32034, 2, 136853, 1527528, 4661087, 2, 227932993, 2, 3689854456, 36278688162, 13749663293, 2, 14084955889019, 5194672859378, 7905858780927, 2977584150505252, 13422745388226152, 2, 1349877580746537123, 2

Offset: 1

Christian G. Bower

a(n) = 2 iff n is prime with a(p) = card{ 1|2|3|...|p-1|p, 123...p } = 2. - Bernard Schott, May 16 2019

			a(4) = card{ 1|2|3|4, 12|34, 14|23, 13|24, 1234 } = 5.
From _Gus Wiseman_, Jul 12 2019: (Start)
The a(6) = 27 set partitions:
  {{1}{2}{3}{4}{5}{6}}  {{12}{34}{56}}  {{123}{456}}  {{123456}}
                        {{12}{35}{46}}  {{124}{356}}
                        {{12}{36}{45}}  {{125}{346}}
                        {{13}{24}{56}}  {{126}{345}}
                        {{13}{25}{46}}  {{134}{256}}
                        {{13}{26}{45}}  {{135}{246}}
                        {{14}{23}{56}}  {{136}{245}}
                        {{14}{25}{36}}  {{145}{236}}
                        {{14}{26}{35}}  {{146}{235}}
                        {{15}{23}{46}}  {{156}{234}}
                        {{15}{24}{36}}
                        {{15}{26}{34}}
                        {{16}{23}{45}}
                        {{16}{24}{35}}
                        {{16}{25}{34}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..250
Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Cf. A061095 (same but with labeled boxes), A005225, A236696, A055225, A262280, A262320.
Column k=1 of A208437.
Row sums of A200472 and A200473.
Cf. A000110, A007837 (different lengths), A035470 (equal sums), A275780, A317583, A320324, A322794, A326512 (equal averages), A326513.

A038041 := proc(n) local d;
add(n!/(d!*(n/d)!^d), d = numtheory[divisors](n)) end:
seq(A038041(n),n = 1..29); # Peter Luschny, Apr 16 2011

a[n_] := Block[{d = Divisors@ n}, Plus @@ (n!/(#! (n/#)!^#) & /@ d)]; Array[a, 29] (* Robert G. Wilson v, Apr 16 2011 *)
Table[Sum[n!/((n/d)!*(d!)^(n/d)), {d, Divisors[n]}], {n, 1, 31}] (* Emanuele Munarini, Jan 30 2014 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],SameQ@@Length/@#&]],{n,0,8}] (* Gus Wiseman, Jul 12 2019 *)

a(n):= lsum(n!/((n/d)!*(d!)^(n/d)),d,listify(divisors(n)));
makelist(a(n),n,1,40); /* Emanuele Munarini, Feb 03 2014 */

/* compare to A061095 */
mnom(v)=
/* Multinomial coefficient s! / prod(j=1, n, v[j]!) where
  s= sum(j=1, n, v[j]) and n is the number of elements in v[]. */
sum(j=1, #v, v[j])! / prod(j=1, #v, v[j]!)
A038041(n)={local(r=0);fordiv(n,d,r+=mnom(vector(d,j,n/d))/d!);return(r);}
vector(33,n,A038041(n)) /* Joerg Arndt, Apr 16 2011 */

import math
def a(n):
    count = 0
    for k in range(1, n + 1):
        if n % k == 0:
            count += math.factorial(n) // (math.factorial(k) ** (n // k) * math.factorial(n // k))
    return count # Paul Muljadi, Sep 25 2024

a(n) = Sum_{d divides n} (n!/(d!*((n/d)!)^d)).

E.g.f.: Sum_{k >= 1} (exp(x^k/k!)-1).

More terms from Erich Friedman

A200473 Irregular triangle read by rows: T(n,k) = number of ways to assign n people to d_k unlabeled groups of equal size (where d_k is the k-th divisor of n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 10, 15, 1, 1, 1, 1, 35, 105, 1, 1, 280, 1, 1, 126, 945, 1, 1, 1, 1, 462, 5775, 15400, 10395, 1, 1, 1, 1, 1716, 135135, 1, 1, 126126, 1401400, 1, 1, 6435, 2627625, 2027025, 1, 1, 1, 1, 24310, 2858856, 190590400, 34459425, 1, 1

Offset: 1

Dennis P. Walsh, Nov 18 2011

This sequence is A200472 with zeros removed.

			T(n,k) begins:
1;
1,      1;
1,      1;
1,      3,       1;
1,      1;
1,     10,      15,       1;
1,      1;
1,     35,     105,       1;
1,    280,       1;
1,    126,     945,       1;
1,      1;
1,    462,    5775,   15400, 10395,   1;
1,      1;
1,   1716,  135135,       1;
1, 126126, 1401400,       1;
1,   6435, 2627625, 2027025,     1;

Alois P. Heinz, Rows n = 1..250, flattened
Dennis P. Walsh, Note on assigning n people to k unlabeled groups of equal size

Cf. A200472, A000005 (row lengths).

Cf. A038041 (row sums).

with(numtheory):
S:= n-> sort([divisors(n)[]]):
T:= (n,k)-> n!/(S(n)[k])!/((n/(S(n)[k]))!)^(S(n)[k]):
seq(seq(T(n, k), k=1..tau(n)), n=1..10);

row[n_] := (n!/#!)/(n/#)!^#& /@ Divisors[n];
Table[row[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Mar 24 2017 *)

T(n,k) = (n!/d_k!)/(n/d_k)!^d_k, n>=1, 1<=k<=tau(n), d_k = k-th divisor of n.

Sum_{k=1..tau(k)} T(n,k) = A038041(n). - Alois P. Heinz, Jul 22 2016

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

Original entry on oeis.org

1, 1, 2, 60, 66360, 4147236820, 19902009929142960, 10325801406739620796634430, 776107138571279347069904891019268480, 10911068841557131648034491574230872615312437194176

Offset: 1

Zacharie Moughanim, Aug 13 2022

nonn

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.

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

Vladimir Ivanov, Table of n, a(n) for n = 1..31
Zacharie Moughanim, Proof of the formula
Wikipedia, Stable Roommates Problem

Cf. A200472.

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

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

cp's OEIS Frontend

A038041 Number of ways to partition an n-set into subsets of equal size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Python

Formula

Extensions

A200473 Irregular triangle read by rows: T(n,k) = number of ways to assign n people to d_k unlabeled groups of equal size (where d_k is the k-th divisor of n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula