The work contains two procedures called  SetPartition  and  NumbPart .

The first procedure  SetPartition  generates all the partitions of a set  S  into disjoint subsets of specific sizes defined by a list  Q. The third optional parameter is the symbol  `ordered`  or  `nonordered`  (by default) . It determines whether the order of subsets in a partition is significant.

The second procedure  NumbPart  returns the number of all partitions of the sizes indicated by  Q .

 

Codes of these procedures:

SetPartition:=proc(S::set, Q::list(posint), K::symbol:=nonordered)  # Procedure finds all partitions of the set  S  into subsets of the specific size given Q.

local L, P, T, S1, S2, n, i, j, m, k, M;

uses ListTools,combinat;

if `+`(op(Q))<>nops(S) then error "Should be `+`(op(Q))=nops(S)" fi;

L:=convert(Q,set);

T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];

P:=`if`(K=ordered,convert(T,list),convert(T,set));

S1:=S;  S2:={`if`(K=ordered,[],{})}; n:=nops(P);

for i to n do

m:=P[i,1]; k:=P[i,2];

for j to k do

S2:={seq(seq(`if`(K=ordered,[op(s),t],{op(s),t}), t=choose(S1 minus `union`(op(s)),m)), s=S2)};

od; od;

if K=ordered then {map(op@permute,S2)[]} else S2 fi;

end proc:

 

NumbPart:=proc(Q::list(posint), K::symbol:=nonordered)  # Procedure finds the number of all partitions of a set into subsets of the specific size given  Q

local L, T, P, n, S, N;

uses ListTools;

L:=convert(Q,set);

T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];

P:=`if`(K=ordered,convert(T,list),convert(T,set));

n:=nops(P);  N:=add(P[i,2], i=1..n);

S:=add(P[i,1]*P[i,2],i=1..n)!/mul(P[i,1]!^P[i,2],i=1..n)/mul(P[i,2]!,i=1..n);

if K=nonordered then return S else  S*N! fi;

end proc:

 

Examples of use:

SetPartition({a,b,c,d,e}, [1,1,3]);  nops(%);  # Nonordered partitions and their number

SetPartition({a,b,c,d,e}, [1,1,3], ordered);  nops(%);  # Ordered partitions and their number

 

 

Here's a more interesting example. 5 fruits  {apple, pear, orange, mango, peach}  must be put on three plates so that  on each of two plates there are 2  fruits, and there is one fruit  on one plate. Two variants to solve: 1) plates are indistinguishable and 2) different plates. In how many ways can this be done?

SetPartition({apple,pear,orange,mango,peach}, [1,2,2]);  nops(%);  # plates are indistinguishable

 

NumbPart([1,2,2], ordered);  # Number of ways for  different plates

                                                              90

 

Another example - how many ways can be divided  100 objects into 10 equal parts?

NumbPart([10$10]);

    64954656894649578274066349293466217242333450230560675312538868633528911487364888307200

 

 SetPartition.mws


Please Wait...