 combinat - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : combinat : combinat/setpartition

combinat

 setpartition
 compute the partitions of a set

 Calling Sequence setpartition(S, m, returnsets)

Parameters

 S - set or list of objects m - (optional) integer indicating the size of the partitions returned returnsets - (optional) to return the partitions as sets even if S is a list

Description

 • The setpartition command returns all the partitions of S. A partition of a set S is a set of subsets of S such that every element s in S is in one and only one of these subsets of the partition, and the union of these subsets is equal to S. A set of $n$ elements has combinat[bell](n) partitions (the $n$th Bell number).
 • If S is a list of objects, then each partition in the output is represented as a list of sublists instead of a set of subsets. By passing the optional argument returnsets = true, each partition in the output will be a set of subsets even if S is a list. Likewise, when passing returnsets = false, each partition will be a list of sublists even if S is a set.
 Note: If S is a list of $n$ elements, with some of them being repeated, the total number of partitions will be smaller than combinat[bell](n) and some elements s of S will appear in more than one sublist of a single partition. For example, when computing all the partitions of $\left[1,1,2\right]$ via setpartition([1, 1, 2]), the partition $\left[\left[1\right],\left[1,2\right]\right]$ appears only once in the result and it contains the element $1$ in two sublists.
 • When the optional argument m is given, each subset is of size m where m must divide the cardinality of the set.

Examples

 > $\mathrm{with}\left(\mathrm{combinat},\mathrm{setpartition}\right)$
 $\left[{\mathrm{setpartition}}\right]$ (1)
 > $S≔\left\{1,2,3,4\right\}$
 ${S}{≔}\left\{{1}{,}{2}{,}{3}{,}{4}\right\}$ (2)
 > $\mathrm{setpartition}\left(S\right)$
 $\left\{\left\{\left\{{1}{,}{2}{,}{3}{,}{4}\right\}\right\}{,}\left\{\left\{{1}\right\}{,}\left\{{2}{,}{3}{,}{4}\right\}\right\}{,}\left\{\left\{{2}\right\}{,}\left\{{1}{,}{3}{,}{4}\right\}\right\}{,}\left\{\left\{{3}\right\}{,}\left\{{1}{,}{2}{,}{4}\right\}\right\}{,}\left\{\left\{{4}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}\right\}{,}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{3}{,}{4}\right\}\right\}{,}\left\{\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{4}\right\}\right\}{,}\left\{\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{3}\right\}\right\}{,}\left\{\left\{{1}\right\}{,}\left\{{2}\right\}{,}\left\{{3}{,}{4}\right\}\right\}{,}\left\{\left\{{1}\right\}{,}\left\{{3}\right\}{,}\left\{{2}{,}{4}\right\}\right\}{,}\left\{\left\{{1}\right\}{,}\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}\right\}{,}\left\{\left\{{2}\right\}{,}\left\{{3}\right\}{,}\left\{{1}{,}{4}\right\}\right\}{,}\left\{\left\{{2}\right\}{,}\left\{{4}\right\}{,}\left\{{1}{,}{3}\right\}\right\}{,}\left\{\left\{{3}\right\}{,}\left\{{4}\right\}{,}\left\{{1}{,}{2}\right\}\right\}{,}\left\{\left\{{1}\right\}{,}\left\{{2}\right\}{,}\left\{{3}\right\}{,}\left\{{4}\right\}\right\}\right\}$ (3)
 > $\mathrm{nops}\left(\right)=\mathrm{combinat}:-\mathrm{bell}\left(4\right)$
 ${15}{=}{15}$ (4)
 > $\mathrm{nops}\left(\mathrm{setpartition}\left(\left[1,2,3,4,5,6,7\right]\right)\right)=\mathrm{combinat}:-\mathrm{bell}\left(7\right)$
 ${877}{=}{877}$ (5)
 > $\mathrm{setpartition}\left(S,2\right)$
 $\left\{\left\{\left\{{1}{,}{2}\right\}{,}\left\{{3}{,}{4}\right\}\right\}{,}\left\{\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{4}\right\}\right\}{,}\left\{\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{3}\right\}\right\}\right\}$ (6)
 > $S≔\left[1,1,3,4\right]$
 ${S}{≔}\left[{1}{,}{1}{,}{3}{,}{4}\right]$ (7)
 > $\mathrm{setpartition}\left(S,2\right)$
 $\left[\left[\left[{1}{,}{1}\right]{,}\left[{3}{,}{4}\right]\right]{,}\left[\left[{1}{,}{3}\right]{,}\left[{1}{,}{4}\right]\right]\right]$ (8)

Compatibility

 • The combinat[setpartition] command was updated in Maple 18.
 • The returnsets option was introduced in Maple 18.