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)
__contains__(x)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4])
sage: all([sp in OS for sp in OS])
True
__init__(s)

TESTS:

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

EXAMPLES:

sage: [ p for p in OrderedSetPartitions([1,2,3]) ]
[[{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}]]
__repr__()

TESTS:

sage: repr(OrderedSetPartitions([1,2,3,4]))
'Ordered set partitions of {1, 2, 3, 4}'
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)
__contains__(x)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1])
sage: all([ sp in OS for sp in OS])
True
sage: OS.cardinality()
12
sage: len(filter(lambda x: x in OS, OrderedSetPartitions([1,2,3,4])))
12
__init__(s, comp)

TESTS:

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

TESTS:

sage: [ p for p in OrderedSetPartitions([1,2,3,4], [2,1,1]) ]
[[{1, 2}, {3}, {4}],
 [{1, 2}, {4}, {3}],
 [{1, 3}, {2}, {4}],
 [{1, 4}, {2}, {3}],
 [{1, 3}, {4}, {2}],
 [{1, 4}, {3}, {2}],
 [{2, 3}, {1}, {4}],
 [{2, 4}, {1}, {3}],
 [{3, 4}, {1}, {2}],
 [{2, 3}, {4}, {1}],
 [{2, 4}, {3}, {1}],
 [{3, 4}, {2}, {1}]]
__repr__()

TESTS:

sage: repr(OrderedSetPartitions([1,2,3,4], [2,1,1]))
'Ordered set partitions of {1, 2, 3, 4} into parts of size [2, 1, 1]'
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)
__contains__(x)

TESTS:

sage: OS = OrderedSetPartitions([1,2,3,4], 2)
sage: all([sp in OS for sp in OS])
True
sage: OS.cardinality()
14
sage: len(filter(lambda x: x in OS, OrderedSetPartitions([1,2,3,4])))
14
__init__(s, n)

TESTS:

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

EXAMPLES:

sage: [ p for p in OrderedSetPartitions([1,2,3,4], 2) ]
[[{1}, {2, 3, 4}],
 [{2}, {1, 3, 4}],
 [{3}, {1, 2, 4}],
 [{4}, {1, 2, 3}],
 [{1, 2}, {3, 4}],
 [{1, 3}, {2, 4}],
 [{1, 4}, {2, 3}],
 [{2, 3}, {1, 4}],
 [{2, 4}, {1, 3}],
 [{3, 4}, {1, 2}],
 [{1, 2, 3}, {4}],
 [{1, 2, 4}, {3}],
 [{1, 3, 4}, {2}],
 [{2, 3, 4}, {1}]]
__repr__()

TESTS:

sage: repr(OrderedSetPartitions([1,2,3,4], 2))
'Ordered set partitions of {1, 2, 3, 4} into 2 parts'
cardinality()

EXAMPLES:

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

Previous topic

q-Analogues

Next topic

Set Partitions

This Page