Ordered Set Partitions

An ordered set partition p of a set s is a partition of s, into subsets called parts and represented 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.

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() #random due to the sets
[[{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() #random due to the sets
[[{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}]]

AUTHORS:

• Mike Hansen
• MuPAD-Combinat developers (for algorithms and design inspiration)

sage.combinat.set_partition_ordered.OrderedSetPartitions(s, c=None)

Returns 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 ['c', 'a', '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'}]]

class sage.combinat.set_partition_ordered.OrderedSetPartitions_s(s)

Bases: sage.combinat.combinat.CombinatorialClass

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.combinat.CombinatorialClass

cardinality()

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.combinat.CombinatorialClass

cardinality()

EXAMPLES:

sage: OrderedSetPartitions(4,2).cardinality()
14
sage: OrderedSetPartitions(4,1).cardinality()
1