AUTHORS:
Bases: sage.structure.list_clone.ClonableArray
An ordered partition of a set.
An ordered set partition of a set
is a list of pairwise
disjoint nonempty subsets of
such that the union of these
subsets is
. 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
is
the set partition of the integers from
to
. The number of
ordered set partitions of
is called the
-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 of ordered set partitions of
is the so-called
-th Fubini number (also
known as the
-th ordered Bell number; see
Wikipedia article Ordered Bell number). Its exponential generating
function is
(See sequence A000670 in OEIS.)
EXAMPLES:
There are 13 ordered set partitions of :
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 whose underlying
composition is
:
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 that we are a valid ordered set partition.
EXAMPLES:
sage: OS = OrderedSetPartitions(4)
sage: s = OS([[1, 3], [2, 4]])
sage: s.check()
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]
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'}]]
alias of OrderedSetPartition
Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions
Class of ordered partitions of a set .
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
Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], [2,1,1])
sage: OS == loads(dumps(OS))
True
Return the cardinality of self.
The number of ordered set partitions of a set of length with
composition shape
is equal to
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
Bases: sage.combinat.set_partition_ordered.OrderedSetPartitions
TESTS:
sage: OS = OrderedSetPartitions([1,2,3,4], 2)
sage: OS == loads(dumps(OS))
True
Return the cardinality of self.
The number of ordered partitions of a set of size into
parts is equal to
where
denotes the Stirling
number of the second kind.
EXAMPLES:
sage: OrderedSetPartitions(4,2).cardinality()
14
sage: OrderedSetPartitions(4,1).cardinality()
1
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