Ordered 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 OrderedSetPartition.
class sage.combinat.set_partition_ordered.OrderedSetPartition(parent, s)

Bases: sage.structure.list_clone.ClonableArray

An ordered partition of a set.

An ordered set partition \(p\) of a set \(s\) is a list of pairwise disjoint nonempty subsets of \(s\) such that the union of these subsets is \(s\). These subsets are called the parts of the partition. We represent an ordered set partition as a list of sets. By extension, an ordered set partition of a nonnegative integer \(n\) is the set partition of the integers from \(1\) to \(n\). The number of ordered set partitions of \(n\) is called the \(n\)-th ordered Bell number.

There is a natural integer composition associated with an ordered set partition, that is the sequence of sizes of all its parts in order.

The number \(T_n\) of ordered set partitions of \(\{ 1, 2, ..., n \}\) is the so-called \(n\)-th Fubini number (also known as the \(n\)-th ordered Bell number; see Wikipedia article Ordered Bell number). Its exponential generating function is

\[\sum_n {T_n \over n!} x^n = {1 \over 2-e^x}.\]

(See sequence A000670 in OEIS.)

EXAMPLES:

There are 13 ordered set partitions of \(\{1,2,3\}\):

sage: OrderedSetPartitions(3).cardinality()
13

Here is the list of them:

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

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

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

Since trac ticket #14140, we can create an ordered set partition directly by OrderedSetPartition 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 ordered set partition from that.

sage: s = OrderedSetPartition([[1,3],[2,4]]); s
[{1, 3}, {2, 4}]
sage: s.parent()
Ordered set partitions of {1, 2, 3, 4}

REFERENCES:

Wikipedia article Ordered_partition_of_a_set

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()
to_composition()

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

EXAMPLES:

sage: S = OrderedSetPartitions(5)
sage: x = S([[3,5,4], [1, 2]])
sage: x.to_composition()
[3, 2]
sage: y = S([[3,1], [2], [5,4]])
sage: y.to_composition()
[2, 1, 2]
class sage.combinat.set_partition_ordered.OrderedSetPartitions(s)

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

Return the combinatorial class of ordered set partitions of s.

EXAMPLES:

sage: OS = OrderedSetPartitions([1,2,3,4]); OS
Ordered set partitions of {1, 2, 3, 4}
sage: OS.cardinality()
75
sage: OS.first()
[{1}, {2}, {3}, {4}]
sage: OS.last()
[{1, 2, 3, 4}]
sage: OS.random_element()
[{3}, {1}, {2}, {4}]
sage: OS = OrderedSetPartitions([1,2,3,4], [2,2]); OS
Ordered set partitions of {1, 2, 3, 4} into parts of size [2, 2]
sage: OS.cardinality()
6
sage: OS.first()
[{1, 2}, {3, 4}]
sage: OS.last()
[{3, 4}, {1, 2}]
sage: OS.list()
[[{1, 2}, {3, 4}],
 [{1, 3}, {2, 4}],
 [{1, 4}, {2, 3}],
 [{2, 3}, {1, 4}],
 [{2, 4}, {1, 3}],
 [{3, 4}, {1, 2}]]
sage: OS = OrderedSetPartitions("cat"); OS
Ordered set partitions of {'a', 'c', 't'}
sage: OS.list()
[[{'a'}, {'c'}, {'t'}],
 [{'a'}, {'t'}, {'c'}],
 [{'c'}, {'a'}, {'t'}],
 [{'t'}, {'a'}, {'c'}],
 [{'c'}, {'t'}, {'a'}],
 [{'t'}, {'c'}, {'a'}],
 [{'a'}, {'c', 't'}],
 [{'c'}, {'a', 't'}],
 [{'t'}, {'a', 'c'}],
 [{'a', 'c'}, {'t'}],
 [{'a', 't'}, {'c'}],
 [{'c', 't'}, {'a'}],
 [{'a', 'c', 't'}]]
Element

alias of OrderedSetPartition

class sage.combinat.set_partition_ordered.OrderedSetPartitions_s(s)

Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions

Class of ordered partitions of a set \(S\).

cardinality()

EXAMPLES:

sage: OrderedSetPartitions(0).cardinality()
1
sage: OrderedSetPartitions(1).cardinality()
1
sage: OrderedSetPartitions(2).cardinality()
3
sage: OrderedSetPartitions(3).cardinality()
13
sage: OrderedSetPartitions([1,2,3]).cardinality()
13
sage: OrderedSetPartitions(4).cardinality()
75
sage: OrderedSetPartitions(5).cardinality()
541
class sage.combinat.set_partition_ordered.OrderedSetPartitions_scomp(s, comp)

Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1])
sage: OS == loads(dumps(OS))
True
cardinality()

Return the cardinality of self.

The number of ordered set partitions of a set of length \(k\) with composition shape \(\mu\) is equal to

\[\frac{k!}{\prod_{\mu_i \neq 0} \mu_i!}.\]

EXAMPLES:

sage: OrderedSetPartitions(5,[2,3]).cardinality()
10
sage: OrderedSetPartitions(0, []).cardinality()
1
sage: OrderedSetPartitions(0, [0]).cardinality()
1
sage: OrderedSetPartitions(0, [0,0]).cardinality()
1
sage: OrderedSetPartitions(5, [2,0,3]).cardinality()
10
class sage.combinat.set_partition_ordered.OrderedSetPartitions_sn(s, n)

Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], 2)
sage: OS == loads(dumps(OS))
True
cardinality()

Return the cardinality of self.

The number of ordered partitions of a set of size \(n\) into \(k\) parts is equal to \(k! S(n,k)\) where \(S(n,k)\) denotes the Stirling number of the second kind.

EXAMPLES:

sage: OrderedSetPartitions(4,2).cardinality()
14
sage: OrderedSetPartitions(4,1).cardinality()
1
class sage.combinat.set_partition_ordered.SplitNK(s, comp)

Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions_scomp

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1])
sage: OS == loads(dumps(OS))
True

Previous topic

Partition tuples

Next topic

Set Partitions

This Page