Set Partitions

AUTHORS:

  • Mike Hansen
  • MuPAD-Combinat developers (for algorithms and design inspiration).
  • Travis Scrimshaw (2013-02-28): Removed CombinatorialClass and added entry point through SetPartition.
  • Martin Rubey (2017-10-10): Cleanup, add crossings and nestings, add random generation.

This module defines a class for immutable partitioning of a set. For mutable version see DisjointSet().

sage.combinat.set_partition.AbstractSetPartition

Methods of set partitions which are independent of the base set

sage.combinat.set_partition.SetPartition

A partition of a set.

A set partition \(p\) of a set \(S\) is a partition of \(S\) into subsets called parts and represented as a set of sets. By extension, a set partition of a nonnegative integer \(n\) is the set partition of the integers from 1 to \(n\). The number of set partitions of \(n\) is called the \(n\)-th Bell number.

There is a natural integer partition associated with a set partition, namely the nonincreasing sequence of sizes of all its parts.

There is a classical lattice associated with all set partitions of \(n\). The infimum of two set partitions is the set partition obtained by intersecting all the parts of both set partitions. The supremum is obtained by transitive closure of the relation \(i\) related to \(j\) if and only if they are in the same part in at least one of the set partitions.

We will use terminology from partitions, in particular the length of a set partition \(A = \{A_1, \ldots, A_k\}\) is the number of parts of \(A\) and is denoted by \(|A| := k\). The size of \(A\) is the cardinality of \(S\). We will also sometimes use the notation \([n] := \{1, 2, \ldots, n\}\).

EXAMPLES:

There are 5 set partitions of the set \(\{1,2,3\}\):

sage: SetPartitions(3).cardinality()
5

Here is the list of them:

sage: SetPartitions(3).list()
[{{1, 2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2, 3}}, {{1}, {2}, {3}}]

There are 6 set partitions of \(\{1,2,3,4\}\) whose underlying partition is \([2, 1, 1]\):

sage: SetPartitions(4, [2,1,1]).list()
[{{1}, {2}, {3, 4}},
 {{1}, {2, 4}, {3}},
 {{1}, {2, 3}, {4}},
 {{1, 4}, {2}, {3}},
 {{1, 3}, {2}, {4}},
 {{1, 2}, {3}, {4}}]

Since trac ticket #14140, we can create a set partition directly by SetPartition, which creates the base set by taking the union of the parts passed in:

sage: s = SetPartition([[1,3],[2,4]]); s
{{1, 3}, {2, 4}}
sage: s.parent()
Set partitions
sage.combinat.set_partition.SetPartitions

An (unordered) partition of a set \(S\) is a set of pairwise disjoint nonempty subsets with union \(S\), and is represented by a sorted list of such subsets.

SetPartitions(s) returns the class of all set partitions of the set s, which can be given as a set or a string; if a string, each character is considered an element.

SetPartitions(n), where n is an integer, returns the class of all set partitions of the set \(\{1, 2, \ldots, n\}\).

You may specify a second argument \(k\). If \(k\) is an integer, SetPartitions returns the class of set partitions into \(k\) parts; if it is an integer partition, SetPartitions returns the class of set partitions whose block sizes correspond to that integer partition.

The Bell number \(B_n\), named in honor of Eric Temple Bell, is the number of different partitions of a set with \(n\) elements.

EXAMPLES:

sage: S = [1,2,3,4]
sage: SetPartitions(S,2)
Set partitions of {1, 2, 3, 4} with 2 parts
sage: SetPartitions([1,2,3,4], [3,1]).list()
[{{1}, {2, 3, 4}}, {{1, 3, 4}, {2}}, {{1, 2, 4}, {3}}, {{1, 2, 3}, {4}}]
sage: SetPartitions(7, [3,3,1]).cardinality()
70

In strings, repeated letters are not considered distinct as of trac ticket #14140:

sage: SetPartitions('abcde').cardinality()
52
sage: SetPartitions('aabcd').cardinality()
15

REFERENCES:

sage.combinat.set_partition.SetPartitions_all

All set partitions.

sage.combinat.set_partition.SetPartitions_set

Set partitions of a fixed set \(S\).

sage.combinat.set_partition.SetPartitions_setn

Set partitions with a given number of blocks.

sage.combinat.set_partition.SetPartitions_setparts

Set partitions with fixed partition sizes corresponding to an integer partition \(\lambda\).

sage.combinat.set_partition.cyclic_permutations_of_set_partition(set_part)

Returns all combinations of cyclic permutations of each cell of the set partition.

AUTHORS:

  • Robert L. Miller

EXAMPLES:

sage: from sage.combinat.set_partition import cyclic_permutations_of_set_partition
sage: cyclic_permutations_of_set_partition([[1,2,3,4],[5,6,7]])
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]
sage.combinat.set_partition.cyclic_permutations_of_set_partition_iterator(set_part)

Iterates over all combinations of cyclic permutations of each cell of the set partition.

AUTHORS:

  • Robert L. Miller

EXAMPLES:

sage: from sage.combinat.set_partition import cyclic_permutations_of_set_partition_iterator
sage: list(cyclic_permutations_of_set_partition_iterator([[1,2,3,4],[5,6,7]]))
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]