46.12 PartitionsSet

PartitionsSet( set )
PartitionsSet( set, k )

NrPartitionsSet( set )
NrPartitionsSet( set, k )

In the first form PartitionsSet returns the set of all unordered partitions of the set set. In the second form PartitionsSet returns the set of all unordered partitions of the set set into k pairwise disjoint nonempty sets.

In the first form NrPartitionsSet returns the number of unordered partitions of the set set. In the second form NrPartitionsSet returns the number of unordered partitions of the set set into k pairwise disjoint nonempty sets.

An unordered partition of set is a set of pairwise disjoint nonempty sets with union set and is represented by a sorted list of such sets. There are B( |set| ) (see Bell) partitions of the set set and S_2( |set|, k ) (see Stirling2) partitions with k elements.

    gap> PartitionsSet( [1,2,3] );
    [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 3 ] ],
      [ [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 2 ] ] ]
    gap> PartitionsSet( [1,2,3,4], 2 );
    [ [ [ 1 ], [ 2, 3, 4 ] ], [ [ 1, 2 ], [ 3, 4 ] ],
      [ [ 1, 2, 3 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ],
      [ [ 1, 3 ], [ 2, 4 ] ], [ [ 1, 3, 4 ], [ 2 ] ],
      [ [ 1, 4 ], [ 2, 3 ] ] ]
    gap> NrPartitionsSet( [1..6] );
    203
    gap> NrPartitionsSet( [1..10], 3 );
    9330 

Note that PartitionsSet does currently not support multisets and that there is currently no ordered counterpart.

Previous Up Top Next
Index