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.
class sage.combinat.set_partition.SetPartition(parent, s)

Bases: sage.structure.list_clone.ClonableArray

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, that is the non-decreasing 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.

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 parent object by taking the union of the partitions passed in. However it is recommended and (marginally) faster to create the parent first and then create the set partition from that.

sage: s = SetPartition([[1,3],[2,4]]); s
{{1, 3}, {2, 4}}
sage: s.parent()
Set partitions of {1, 2, 3, 4}
apply_permutation(p)

Apply p to the underlying set of self.

INPUT:

  • p – A permutation

EXAMPLES:

sage: x = SetPartition([[1,2], [3,5,4]])
sage: p = Permutation([2,1,4,5,3])
sage: x.apply_permutation(p)
{{1, 2}, {3, 4, 5}}
sage: q = Permutation([3,2,1,5,4])
sage: x.apply_permutation(q)
{{1, 4, 5}, {2, 3}}
cardinality()

Returns the len of self

EXAMPLES:

sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: len(IncreasingArrays()([1,2,3]))
3
check()

Check that we are a valid ordered set partition.

EXAMPLES:

sage: OS = OrderedSetPartitions(4)
sage: s = OS([[1, 3], [2, 4]])
sage: s.check()
inf(t)

Return the infimum of self and t in the classical set partition lattice.

The infimum of two set partitions is the set partition obtained by intersecting all the parts of both set partitions.

EXAMPLES:

sage: S = SetPartitions(4)
sage: sp1 = S([[2,3,4], [1]])
sage: sp2 = S([[1,3], [2,4]])
sage: s = S([[2,4], [3], [1]])
sage: sp1.inf(sp2) == s
True
is_noncrossing()

Check if self is non crossing.

EXAMPLES:

sage: x = SetPartition([[1,2],[3,4]])
sage: x.is_noncrossing()
True
sage: x = SetPartition([[1,3],[2,4]])
sage: x.is_noncrossing()
False

AUTHOR: Florent Hivert

shape(*args, **kwds)

Return the integer partition whose parts are the sizes of the sets in self.

EXAMPLES:

sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
shape_partition(*args, **kwds)

Return the integer partition whose parts are the sizes of the sets in self.

EXAMPLES:

sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
standard_form()

Return self as a list of lists.

EXAMPLES:

sage: [x.standard_form() for x in SetPartitions(4, [2,2])]
[[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[1, 4], [2, 3]]]
sup(t)

Return the supremum of self and t in the classical set partition lattice.

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.

EXAMPLES:

sage: S = SetPartitions(4)
sage: sp1 = S([[2,3,4], [1]])
sage: sp2 = S([[1,3], [2,4]])
sage: s = S([[1,2,3,4]])
sage: sp1.sup(sp2) == s
True
to_partition(*args, **kwds)

Return the integer partition whose parts are the sizes of the sets in self.

EXAMPLES:

sage: S = SetPartitions(5)
sage: x = S([[1,2], [3,5,4]])
sage: x.shape()
[3, 2]
sage: y = S([[2], [3,1], [5,4]])
sage: y.shape()
[2, 2, 1]
to_permutation(*args, **kwds)

Convert self to a permutation by considering the partitions as cycles.

EXAMPLES:

sage: s = SetPartition([[1,3],[2,4]])
sage: s.to_permutation()
[3, 4, 1, 2]
class sage.combinat.set_partition.SetPartitions(s)

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

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 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:

Element

alias of SetPartition

is_less_than(s, t)

Check if s < t in the ordering on set partitions.

EXAMPLES:

sage: S = SetPartitions(4)
sage: s = S([[1,3],[2,4]])
sage: t = S([[1],[2],[3],[4]])
sage: S.is_less_than(t, s)
True
lt(s, t)

Check if s < t in the ordering on set partitions.

EXAMPLES:

sage: S = SetPartitions(4)
sage: s = S([[1,3],[2,4]])
sage: t = S([[1],[2],[3],[4]])
sage: S.is_less_than(t, s)
True
class sage.combinat.set_partition.SetPartitions_set(s)

Bases: sage.combinat.set_partition.SetPartitions

Set partitions of a fixed set S.

cardinality()

Return the number of set partitions of the set S.

The cardinality is given by the n-th Bell number where n is the number of elements in the set S.

EXAMPLES:

sage: SetPartitions([1,2,3,4]).cardinality()
15
sage: SetPartitions(3).cardinality()
5
sage: SetPartitions(3,2).cardinality()
3
sage: SetPartitions([]).cardinality()
1
class sage.combinat.set_partition.SetPartitions_setn(s, n)

Bases: sage.combinat.set_partition.SetPartitions

TESTS:

sage: S = SetPartitions(5, 3)
sage: TestSuite(S).run()
cardinality()

The Stirling number of the second kind is the number of partitions of a set of size n into k blocks.

EXAMPLES:

sage: SetPartitions(5, 3).cardinality()
25
sage: stirling_number2(5,3)
25
class sage.combinat.set_partition.SetPartitions_setparts(s, parts)

Bases: sage.combinat.set_partition.SetPartitions

Class of all set partitions with fixed partition sizes corresponding to and integer partition \lambda.

cardinality()

Return the cardinality of self.

EXAMPLES:

sage: SetPartitions(3, [2,1]).cardinality()
3
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]]]
sage.combinat.set_partition.inf(s, t)

Deprecated in trac ticket #14140. Use SetPartition.inf() instead.

EXAMPLES:

sage: sp1 = Set([Set([2,3,4]),Set([1])])
sage: sp2 = Set([Set([1,3]), Set([2,4])])
sage: s = Set([ Set([2,4]), Set([3]), Set([1])]) #{{2, 4}, {3}, {1}}
sage: sage.combinat.set_partition.inf(sp1, sp2) == s
doctest:1: DeprecationWarning: inf(s, t) is deprecated. Use s.inf(t) instead.
See http://trac.sagemath.org/14140 for details.
True
sage.combinat.set_partition.less(s, t)

Deprecated in trac ticket #14140. Use SetPartitions.is_less_than() instead.

EXAMPLES:

sage: z = SetPartitions(3).list()
sage: sage.combinat.set_partition.less(z[0], z[1])
doctest:1: DeprecationWarning: less(s, t) is deprecated. Use SetPartitions.is_less_tan(s, t) instead.
See http://trac.sagemath.org/14140 for details.
False
sage.combinat.set_partition.standard_form(sp)

Deprecated in trac ticket #14140. Use SetPartition.standard_form() instead.

EXAMPLES:

sage: map(sage.combinat.set_partition.standard_form, SetPartitions(4, [2,2]))
doctest:1: DeprecationWarning: standard_form(sp) is deprecated. Use sp.standard_form() instead.
See http://trac.sagemath.org/14140 for details.
[[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[1, 4], [2, 3]]]
sage.combinat.set_partition.sup(s, t)

Deprecated in trac ticket #14140. Use SetPartition.sup() instead.

EXAMPLES:

sage: sp1 = Set([Set([2,3,4]),Set([1])])
sage: sp2 = Set([Set([1,3]), Set([2,4])])
sage: s = Set([ Set([1,2,3,4]) ])
sage: sage.combinat.set_partition.sup(sp1, sp2) == s
doctest:1: DeprecationWarning: sup(s, t) is deprecated. Use s.sup(t) instead.
See http://trac.sagemath.org/14140 for details.
True

Previous topic

Ordered Set Partitions

Next topic

Abstract Recursive Trees

This Page