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, check=True)[source]

Bases: 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, \ldots, 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 \frac{T_n}{n!} x^n = \frac{1}{2-e^x}.\]

(See sequence OEIS sequence A000670 in OEIS.)

INPUT:

  • parts – an object or iterable that defines an ordered set partition (e.g., a list of pairwise disjoint sets) or a packed word (e.g., a list of letters on some alphabet). If there is ambiguity and if the input should be treated as a packed word, the keyword from_word should be used.

EXAMPLES:

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

sage: OrderedSetPartitions(3).cardinality()
13

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(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}]]

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(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}]]

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(4),[Integer(1),Integer(2),Integer(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 Issue #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}

>>> from sage.all import *
>>> s = OrderedSetPartition([[Integer(1),Integer(3)],[Integer(2),Integer(4)]]); s
[{1, 3}, {2, 4}]
>>> s.parent()
Ordered set partitions of {1, 2, 3, 4}

We can construct the ordered set partition from a word, which we consider as packed:

sage: OrderedSetPartition([2,4,1,2])
[{3}, {1, 4}, {2}]
sage: OrderedSetPartition(from_word=[2,4,1,2])
[{3}, {1, 4}, {2}]
sage: OrderedSetPartition(from_word='bdab')
[{3}, {1, 4}, {2}]

>>> from sage.all import *
>>> OrderedSetPartition([Integer(2),Integer(4),Integer(1),Integer(2)])
[{3}, {1, 4}, {2}]
>>> OrderedSetPartition(from_word=[Integer(2),Integer(4),Integer(1),Integer(2)])
[{3}, {1, 4}, {2}]
>>> OrderedSetPartition(from_word='bdab')
[{3}, {1, 4}, {2}]

Warning

The elements of the underlying set should be hashable.

REFERENCES:

Wikipedia article Ordered_partition_of_a_set

base_set()[source]

Return the base set of self.

This is the union of all parts of self.

EXAMPLES:

sage: OrderedSetPartition([[1], [2,3], [4]]).base_set()
frozenset({1, 2, 3, 4})
sage: OrderedSetPartition([[1,2,3,4]]).base_set()
frozenset({1, 2, 3, 4})
sage: OrderedSetPartition([]).base_set()
frozenset()

>>> from sage.all import *
>>> OrderedSetPartition([[Integer(1)], [Integer(2),Integer(3)], [Integer(4)]]).base_set()
frozenset({1, 2, 3, 4})
>>> OrderedSetPartition([[Integer(1),Integer(2),Integer(3),Integer(4)]]).base_set()
frozenset({1, 2, 3, 4})
>>> OrderedSetPartition([]).base_set()
frozenset()
base_set_cardinality()[source]

Return the cardinality of the base set of self.

This is the sum of the sizes of the parts of self.

This is also known as the size (sometimes the weight) of an ordered set partition.

EXAMPLES:

sage: OrderedSetPartition([[1], [2,3], [4]]).base_set_cardinality()
4
sage: OrderedSetPartition([[1,2,3,4]]).base_set_cardinality()
4

>>> from sage.all import *
>>> OrderedSetPartition([[Integer(1)], [Integer(2),Integer(3)], [Integer(4)]]).base_set_cardinality()
4
>>> OrderedSetPartition([[Integer(1),Integer(2),Integer(3),Integer(4)]]).base_set_cardinality()
4
static bottom_up_osp(X, comp)[source]

Return the ordered set partition obtained by listing the elements of the set X in increasing order, and placing bars between some of them according to the integer composition comp (namely, the bars are placed in such a way that the lengths of the resulting blocks are exactly the entries of comp).

INPUT:

  • X – a finite set (or list or tuple)

  • comp – a composition whose sum is the size of X (can be given as a list or tuple or composition)

EXAMPLES:

sage: buo = OrderedSetPartition.bottom_up_osp
sage: buo(Set([1, 4, 7, 9]), [2, 1, 1])
[{1, 4}, {7}, {9}]
sage: buo(Set([1, 4, 7, 9]), [1, 3])
[{1}, {4, 7, 9}]
sage: buo(Set([1, 4, 7, 9]), [1, 1, 1, 1])
[{1}, {4}, {7}, {9}]
sage: buo(range(8), [1, 4, 2, 1])
[{0}, {1, 2, 3, 4}, {5, 6}, {7}]
sage: buo([], [])
[]

>>> from sage.all import *
>>> buo = OrderedSetPartition.bottom_up_osp
>>> buo(Set([Integer(1), Integer(4), Integer(7), Integer(9)]), [Integer(2), Integer(1), Integer(1)])
[{1, 4}, {7}, {9}]
>>> buo(Set([Integer(1), Integer(4), Integer(7), Integer(9)]), [Integer(1), Integer(3)])
[{1}, {4, 7, 9}]
>>> buo(Set([Integer(1), Integer(4), Integer(7), Integer(9)]), [Integer(1), Integer(1), Integer(1), Integer(1)])
[{1}, {4}, {7}, {9}]
>>> buo(range(Integer(8)), [Integer(1), Integer(4), Integer(2), Integer(1)])
[{0}, {1, 2, 3, 4}, {5, 6}, {7}]
>>> buo([], [])
[]
check()[source]

Check that we are a valid ordered set partition.

EXAMPLES:

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

>>> from sage.all import *
>>> OS = OrderedSetPartitions(Integer(4))
>>> s = OS([[Integer(1), Integer(3)], [Integer(2), Integer(4)]])
>>> s.check()
complement()[source]

Return the complement of the ordered set partition self.

This assumes that self is an ordered set partition of an interval of \(\ZZ\).

Let \((P_1, P_2, \ldots, P_k)\) be an ordered set partition of some interval \(I\) of \(\ZZ\). Let \(\omega\) be the unique strictly decreasing bijection \(I \to I\). Then, the complement of \((P_1, P_2, \ldots, P_k)\) is defined to be the ordered set partition \((\omega(P_1), \omega(P_2), \ldots, \omega(P_k))\).

EXAMPLES:

sage: OrderedSetPartition([[1, 2], [3]]).complement()
[{2, 3}, {1}]
sage: OrderedSetPartition([[1, 3], [2]]).complement()
[{1, 3}, {2}]
sage: OrderedSetPartition([[2, 3]]).complement()
[{2, 3}]
sage: OrderedSetPartition([[1, 5], [2, 3], [4]]).complement()
[{1, 5}, {3, 4}, {2}]
sage: OrderedSetPartition([[-1], [-2], [1, 2], [0]]).complement()
[{1}, {2}, {-2, -1}, {0}]
sage: OrderedSetPartition([]).complement()
[]

>>> from sage.all import *
>>> OrderedSetPartition([[Integer(1), Integer(2)], [Integer(3)]]).complement()
[{2, 3}, {1}]
>>> OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]]).complement()
[{1, 3}, {2}]
>>> OrderedSetPartition([[Integer(2), Integer(3)]]).complement()
[{2, 3}]
>>> OrderedSetPartition([[Integer(1), Integer(5)], [Integer(2), Integer(3)], [Integer(4)]]).complement()
[{1, 5}, {3, 4}, {2}]
>>> OrderedSetPartition([[-Integer(1)], [-Integer(2)], [Integer(1), Integer(2)], [Integer(0)]]).complement()
[{1}, {2}, {-2, -1}, {0}]
>>> OrderedSetPartition([]).complement()
[]
fatten(grouping)[source]

Return the ordered set partition fatter than self, obtained by grouping together consecutive parts according to the integer composition grouping.

See finer() for the definition of “fatter”.

INPUT:

  • grouping – a composition whose sum is the length of self

EXAMPLES:

Let us start with the ordered set partition:

sage: c = OrderedSetPartition([[2, 5], [1], [3, 4]])

>>> from sage.all import *
>>> c = OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1)], [Integer(3), Integer(4)]])

With grouping equal to \((1, \ldots, 1)\), \(c\) is left unchanged:

sage: c.fatten(Composition([1,1,1]))
[{2, 5}, {1}, {3, 4}]

>>> from sage.all import *
>>> c.fatten(Composition([Integer(1),Integer(1),Integer(1)]))
[{2, 5}, {1}, {3, 4}]

With grouping equal to \((\ell)\) where \(\ell\) is the length of \(c\), this yields the coarsest ordered set partition above \(c\):

sage: c.fatten(Composition([3]))
[{1, 2, 3, 4, 5}]

>>> from sage.all import *
>>> c.fatten(Composition([Integer(3)]))
[{1, 2, 3, 4, 5}]

Other values for grouping yield (all the) other ordered set partitions coarser than \(c\):

sage: c.fatten(Composition([2,1]))
[{1, 2, 5}, {3, 4}]
sage: c.fatten(Composition([1,2]))
[{2, 5}, {1, 3, 4}]

>>> from sage.all import *
>>> c.fatten(Composition([Integer(2),Integer(1)]))
[{1, 2, 5}, {3, 4}]
>>> c.fatten(Composition([Integer(1),Integer(2)]))
[{2, 5}, {1, 3, 4}]
fatter()[source]

Return the set of ordered set partitions which are fatter than self.

See finer() for the definition of “fatter”.

EXAMPLES:

sage: C = OrderedSetPartition([[2, 5], [1], [3, 4]]).fatter()
sage: C.cardinality()
4
sage: sorted(C)
[[{2, 5}, {1}, {3, 4}],
 [{2, 5}, {1, 3, 4}],
 [{1, 2, 5}, {3, 4}],
 [{1, 2, 3, 4, 5}]]

sage: OrderedSetPartition([[4, 9], [-1, 2]]).fatter().list()
[[{4, 9}, {-1, 2}], [{-1, 2, 4, 9}]]

>>> from sage.all import *
>>> C = OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1)], [Integer(3), Integer(4)]]).fatter()
>>> C.cardinality()
4
>>> sorted(C)
[[{2, 5}, {1}, {3, 4}],
 [{2, 5}, {1, 3, 4}],
 [{1, 2, 5}, {3, 4}],
 [{1, 2, 3, 4, 5}]]

>>> OrderedSetPartition([[Integer(4), Integer(9)], [-Integer(1), Integer(2)]]).fatter().list()
[[{4, 9}, {-1, 2}], [{-1, 2, 4, 9}]]

Some extreme cases:

sage: list(OrderedSetPartition([[5]]).fatter())
[[{5}]]
sage: list(Composition([]).fatter())
[[]]
sage: sorted(OrderedSetPartition([[1], [2], [3], [4]]).fatter())
[[{1}, {2}, {3}, {4}],
 [{1}, {2}, {3, 4}],
 [{1}, {2, 3}, {4}],
 [{1}, {2, 3, 4}],
 [{1, 2}, {3}, {4}],
 [{1, 2}, {3, 4}],
 [{1, 2, 3}, {4}],
 [{1, 2, 3, 4}]]

>>> from sage.all import *
>>> list(OrderedSetPartition([[Integer(5)]]).fatter())
[[{5}]]
>>> list(Composition([]).fatter())
[[]]
>>> sorted(OrderedSetPartition([[Integer(1)], [Integer(2)], [Integer(3)], [Integer(4)]]).fatter())
[[{1}, {2}, {3}, {4}],
 [{1}, {2}, {3, 4}],
 [{1}, {2, 3}, {4}],
 [{1}, {2, 3, 4}],
 [{1, 2}, {3}, {4}],
 [{1, 2}, {3, 4}],
 [{1, 2, 3}, {4}],
 [{1, 2, 3, 4}]]
finer()[source]

Return the set of ordered set partitions which are finer than self.

See is_finer() for the definition of “finer”.

EXAMPLES:

sage: C = OrderedSetPartition([[1, 3], [2]]).finer()
sage: C.cardinality()
3
sage: C.list()
[[{1}, {3}, {2}], [{3}, {1}, {2}], [{1, 3}, {2}]]

sage: OrderedSetPartition([]).finer()
{[]}

sage: W = OrderedSetPartition([[4, 9], [-1, 2]])
sage: W.finer().list()
[[{9}, {4}, {2}, {-1}],
 [{9}, {4}, {-1}, {2}],
 [{9}, {4}, {-1, 2}],
 [{4}, {9}, {2}, {-1}],
 [{4}, {9}, {-1}, {2}],
 [{4}, {9}, {-1, 2}],
 [{4, 9}, {2}, {-1}],
 [{4, 9}, {-1}, {2}],
 [{4, 9}, {-1, 2}]]

>>> from sage.all import *
>>> C = OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]]).finer()
>>> C.cardinality()
3
>>> C.list()
[[{1}, {3}, {2}], [{3}, {1}, {2}], [{1, 3}, {2}]]

>>> OrderedSetPartition([]).finer()
{[]}

>>> W = OrderedSetPartition([[Integer(4), Integer(9)], [-Integer(1), Integer(2)]])
>>> W.finer().list()
[[{9}, {4}, {2}, {-1}],
 [{9}, {4}, {-1}, {2}],
 [{9}, {4}, {-1, 2}],
 [{4}, {9}, {2}, {-1}],
 [{4}, {9}, {-1}, {2}],
 [{4}, {9}, {-1, 2}],
 [{4, 9}, {2}, {-1}],
 [{4, 9}, {-1}, {2}],
 [{4, 9}, {-1, 2}]]
is_finer(co2)[source]

Return True if the ordered set partition self is finer than the ordered set partition co2; otherwise, return False.

If \(A\) and \(B\) are two ordered set partitions of the same set, then \(A\) is said to be finer than \(B\) if \(B\) can be obtained from \(A\) by (repeatedly) merging consecutive parts. In this case, we say that \(B\) is fatter than \(A\).

EXAMPLES:

sage: A = OrderedSetPartition([[1, 3], [2]])
sage: B = OrderedSetPartition([[1], [3], [2]])
sage: A.is_finer(B)
False
sage: B.is_finer(A)
True
sage: C = OrderedSetPartition([[3], [1], [2]])
sage: A.is_finer(C)
False
sage: C.is_finer(A)
True
sage: OrderedSetPartition([[2], [5], [1], [4]]).is_finer(OrderedSetPartition([[2, 5], [1, 4]]))
True
sage: OrderedSetPartition([[5], [2], [1], [4]]).is_finer(OrderedSetPartition([[2, 5], [1, 4]]))
True
sage: OrderedSetPartition([[2], [1], [5], [4]]).is_finer(OrderedSetPartition([[2, 5], [1, 4]]))
False
sage: OrderedSetPartition([[2, 5, 1], [4]]).is_finer(OrderedSetPartition([[2, 5], [1, 4]]))
False

>>> from sage.all import *
>>> A = OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]])
>>> B = OrderedSetPartition([[Integer(1)], [Integer(3)], [Integer(2)]])
>>> A.is_finer(B)
False
>>> B.is_finer(A)
True
>>> C = OrderedSetPartition([[Integer(3)], [Integer(1)], [Integer(2)]])
>>> A.is_finer(C)
False
>>> C.is_finer(A)
True
>>> OrderedSetPartition([[Integer(2)], [Integer(5)], [Integer(1)], [Integer(4)]]).is_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
True
>>> OrderedSetPartition([[Integer(5)], [Integer(2)], [Integer(1)], [Integer(4)]]).is_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
True
>>> OrderedSetPartition([[Integer(2)], [Integer(1)], [Integer(5)], [Integer(4)]]).is_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
False
>>> OrderedSetPartition([[Integer(2), Integer(5), Integer(1)], [Integer(4)]]).is_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
False
is_strongly_finer(co2)[source]

Return True if the ordered set partition self is strongly finer than the ordered set partition co2; otherwise, return False.

If \(A\) and \(B\) are two ordered set partitions of the same set, then \(A\) is said to be strongly finer than \(B\) if \(B\) can be obtained from \(A\) by (repeatedly) merging consecutive parts, provided that every time we merge two consecutive parts \(C_i\) and \(C_{i+1}\), we have \(\max C_i < \min C_{i+1}\). In this case, we say that \(B\) is strongly fatter than \(A\).

EXAMPLES:

sage: A = OrderedSetPartition([[1, 3], [2]])
sage: B = OrderedSetPartition([[1], [3], [2]])
sage: A.is_strongly_finer(B)
False
sage: B.is_strongly_finer(A)
True
sage: C = OrderedSetPartition([[3], [1], [2]])
sage: A.is_strongly_finer(C)
False
sage: C.is_strongly_finer(A)
False
sage: OrderedSetPartition([[2], [5], [1], [4]]).is_strongly_finer(OrderedSetPartition([[2, 5], [1, 4]]))
True
sage: OrderedSetPartition([[5], [2], [1], [4]]).is_strongly_finer(OrderedSetPartition([[2, 5], [1, 4]]))
False
sage: OrderedSetPartition([[2], [1], [5], [4]]).is_strongly_finer(OrderedSetPartition([[2, 5], [1, 4]]))
False
sage: OrderedSetPartition([[2, 5, 1], [4]]).is_strongly_finer(OrderedSetPartition([[2, 5], [1, 4]]))
False

>>> from sage.all import *
>>> A = OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]])
>>> B = OrderedSetPartition([[Integer(1)], [Integer(3)], [Integer(2)]])
>>> A.is_strongly_finer(B)
False
>>> B.is_strongly_finer(A)
True
>>> C = OrderedSetPartition([[Integer(3)], [Integer(1)], [Integer(2)]])
>>> A.is_strongly_finer(C)
False
>>> C.is_strongly_finer(A)
False
>>> OrderedSetPartition([[Integer(2)], [Integer(5)], [Integer(1)], [Integer(4)]]).is_strongly_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
True
>>> OrderedSetPartition([[Integer(5)], [Integer(2)], [Integer(1)], [Integer(4)]]).is_strongly_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
False
>>> OrderedSetPartition([[Integer(2)], [Integer(1)], [Integer(5)], [Integer(4)]]).is_strongly_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
False
>>> OrderedSetPartition([[Integer(2), Integer(5), Integer(1)], [Integer(4)]]).is_strongly_finer(OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1), Integer(4)]]))
False
length()[source]

Return the number of parts of self.

EXAMPLES:

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

>>> from sage.all import *
>>> OS = OrderedSetPartitions(Integer(4))
>>> s = OS([[Integer(1), Integer(3)], [Integer(2), Integer(4)]])
>>> s.length()
2
number_of_inversions()[source]

Return the number of inversions in self.

An inversion of an ordered set partition with blocks \([B_1,B_2, \ldots, B_k]\) is a pair of letters \(i\) and \(j\) with \(i < j\) such that \(i\) is minimal in \(B_m\), \(j \in B_l\), and \(l < m\).

REFERENCES:

EXAMPLES:

sage: OrderedSetPartition([{2,5},{4,6},{1,3}]).number_of_inversions()
5
sage: OrderedSetPartition([{1,3,8},{2,4},{5,6,7}]).number_of_inversions()
3

>>> from sage.all import *
>>> OrderedSetPartition([{Integer(2),Integer(5)},{Integer(4),Integer(6)},{Integer(1),Integer(3)}]).number_of_inversions()
5
>>> OrderedSetPartition([{Integer(1),Integer(3),Integer(8)},{Integer(2),Integer(4)},{Integer(5),Integer(6),Integer(7)}]).number_of_inversions()
3
reversed()[source]

Return the reversal of the ordered set partition self.

The reversal of an ordered set partition \((P_1, P_2, \ldots, P_k)\) is defined to be the ordered set partition \((P_k, P_{k-1}, \ldots, P_1)\).

EXAMPLES:

sage: OrderedSetPartition([[1, 3], [2]]).reversed()
[{2}, {1, 3}]
sage: OrderedSetPartition([[1, 5], [2, 4]]).reversed()
[{2, 4}, {1, 5}]
sage: OrderedSetPartition([[-1], [-2], [3, 4], [0]]).reversed()
[{0}, {3, 4}, {-2}, {-1}]
sage: OrderedSetPartition([]).reversed()
[]

>>> from sage.all import *
>>> OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]]).reversed()
[{2}, {1, 3}]
>>> OrderedSetPartition([[Integer(1), Integer(5)], [Integer(2), Integer(4)]]).reversed()
[{2, 4}, {1, 5}]
>>> OrderedSetPartition([[-Integer(1)], [-Integer(2)], [Integer(3), Integer(4)], [Integer(0)]]).reversed()
[{0}, {3, 4}, {-2}, {-1}]
>>> OrderedSetPartition([]).reversed()
[]
size()[source]

Return the cardinality of the base set of self.

This is the sum of the sizes of the parts of self.

This is also known as the size (sometimes the weight) of an ordered set partition.

EXAMPLES:

sage: OrderedSetPartition([[1], [2,3], [4]]).base_set_cardinality()
4
sage: OrderedSetPartition([[1,2,3,4]]).base_set_cardinality()
4

>>> from sage.all import *
>>> OrderedSetPartition([[Integer(1)], [Integer(2),Integer(3)], [Integer(4)]]).base_set_cardinality()
4
>>> OrderedSetPartition([[Integer(1),Integer(2),Integer(3),Integer(4)]]).base_set_cardinality()
4
strongly_fatter()[source]

Return the set of ordered set partitions which are strongly fatter than self.

See strongly_finer() for the definition of “strongly fatter”.

EXAMPLES:

sage: C = OrderedSetPartition([[2, 5], [1], [3, 4]]).strongly_fatter()
sage: C.cardinality()
2
sage: sorted(C)
[[{2, 5}, {1}, {3, 4}], [{2, 5}, {1, 3, 4}]]

sage: OrderedSetPartition([[4, 9], [-1, 2]]).strongly_fatter().list()
[[{4, 9}, {-1, 2}]]

>>> from sage.all import *
>>> C = OrderedSetPartition([[Integer(2), Integer(5)], [Integer(1)], [Integer(3), Integer(4)]]).strongly_fatter()
>>> C.cardinality()
2
>>> sorted(C)
[[{2, 5}, {1}, {3, 4}], [{2, 5}, {1, 3, 4}]]

>>> OrderedSetPartition([[Integer(4), Integer(9)], [-Integer(1), Integer(2)]]).strongly_fatter().list()
[[{4, 9}, {-1, 2}]]

Some extreme cases:

sage: list(OrderedSetPartition([[5]]).strongly_fatter())
[[{5}]]
sage: list(OrderedSetPartition([]).strongly_fatter())
[[]]
sage: sorted(OrderedSetPartition([[1], [2], [3], [4]]).strongly_fatter())
[[{1}, {2}, {3}, {4}],
 [{1}, {2}, {3, 4}],
 [{1}, {2, 3}, {4}],
 [{1}, {2, 3, 4}],
 [{1, 2}, {3}, {4}],
 [{1, 2}, {3, 4}],
 [{1, 2, 3}, {4}],
 [{1, 2, 3, 4}]]
sage: sorted(OrderedSetPartition([[1], [3], [2], [4]]).strongly_fatter())
[[{1}, {3}, {2}, {4}],
 [{1}, {3}, {2, 4}],
 [{1, 3}, {2}, {4}],
 [{1, 3}, {2, 4}]]
sage: sorted(OrderedSetPartition([[4], [1], [5], [3]]).strongly_fatter())
[[{4}, {1}, {5}, {3}], [{4}, {1, 5}, {3}]]

>>> from sage.all import *
>>> list(OrderedSetPartition([[Integer(5)]]).strongly_fatter())
[[{5}]]
>>> list(OrderedSetPartition([]).strongly_fatter())
[[]]
>>> sorted(OrderedSetPartition([[Integer(1)], [Integer(2)], [Integer(3)], [Integer(4)]]).strongly_fatter())
[[{1}, {2}, {3}, {4}],
 [{1}, {2}, {3, 4}],
 [{1}, {2, 3}, {4}],
 [{1}, {2, 3, 4}],
 [{1, 2}, {3}, {4}],
 [{1, 2}, {3, 4}],
 [{1, 2, 3}, {4}],
 [{1, 2, 3, 4}]]
>>> sorted(OrderedSetPartition([[Integer(1)], [Integer(3)], [Integer(2)], [Integer(4)]]).strongly_fatter())
[[{1}, {3}, {2}, {4}],
 [{1}, {3}, {2, 4}],
 [{1, 3}, {2}, {4}],
 [{1, 3}, {2, 4}]]
>>> sorted(OrderedSetPartition([[Integer(4)], [Integer(1)], [Integer(5)], [Integer(3)]]).strongly_fatter())
[[{4}, {1}, {5}, {3}], [{4}, {1, 5}, {3}]]
strongly_finer()[source]

Return the set of ordered set partitions which are strongly finer than self.

See is_strongly_finer() for the definition of “strongly finer”.

EXAMPLES:

sage: C = OrderedSetPartition([[1, 3], [2]]).strongly_finer()
sage: C.cardinality()
2
sage: C.list()
[[{1}, {3}, {2}], [{1, 3}, {2}]]

sage: OrderedSetPartition([]).strongly_finer()
{[]}

sage: W = OrderedSetPartition([[4, 9], [-1, 2]])
sage: W.strongly_finer().list()
[[{4}, {9}, {-1}, {2}],
 [{4}, {9}, {-1, 2}],
 [{4, 9}, {-1}, {2}],
 [{4, 9}, {-1, 2}]]

>>> from sage.all import *
>>> C = OrderedSetPartition([[Integer(1), Integer(3)], [Integer(2)]]).strongly_finer()
>>> C.cardinality()
2
>>> C.list()
[[{1}, {3}, {2}], [{1, 3}, {2}]]

>>> OrderedSetPartition([]).strongly_finer()
{[]}

>>> W = OrderedSetPartition([[Integer(4), Integer(9)], [-Integer(1), Integer(2)]])
>>> W.strongly_finer().list()
[[{4}, {9}, {-1}, {2}],
 [{4}, {9}, {-1, 2}],
 [{4, 9}, {-1}, {2}],
 [{4, 9}, {-1, 2}]]
static sum(osps)[source]

Return the concatenation of the given ordered set partitions osps (provided they have no elements in common).

INPUT:

  • osps – list (or iterable) of ordered set partitions

EXAMPLES:

sage: OrderedSetPartition.sum([OrderedSetPartition([[4, 1], [3]]), OrderedSetPartition([[7], [2]]), OrderedSetPartition([[5, 6]])])
[{1, 4}, {3}, {7}, {2}, {5, 6}]

>>> from sage.all import *
>>> OrderedSetPartition.sum([OrderedSetPartition([[Integer(4), Integer(1)], [Integer(3)]]), OrderedSetPartition([[Integer(7)], [Integer(2)]]), OrderedSetPartition([[Integer(5), Integer(6)]])])
[{1, 4}, {3}, {7}, {2}, {5, 6}]

Any iterable can be provided as input:

sage: OrderedSetPartition.sum([OrderedSetPartition([[2*i,2*i+1]]) for i in [4,1,3]])
[{8, 9}, {2, 3}, {6, 7}]

>>> from sage.all import *
>>> OrderedSetPartition.sum([OrderedSetPartition([[Integer(2)*i,Integer(2)*i+Integer(1)]]) for i in [Integer(4),Integer(1),Integer(3)]])
[{8, 9}, {2, 3}, {6, 7}]

Empty inputs are handled gracefully:

sage: OrderedSetPartition.sum([]) == OrderedSetPartition([])
True

>>> from sage.all import *
>>> OrderedSetPartition.sum([]) == OrderedSetPartition([])
True
to_composition()[source]

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]

>>> from sage.all import *
>>> S = OrderedSetPartitions(Integer(5))
>>> x = S([[Integer(3),Integer(5),Integer(4)], [Integer(1), Integer(2)]])
>>> x.to_composition()
[3, 2]
>>> y = S([[Integer(3),Integer(1)], [Integer(2)], [Integer(5),Integer(4)]])
>>> y.to_composition()
[2, 1, 2]
to_packed_word()[source]

Return the packed word on alphabet \(\{1,2,3,\ldots\}\) corresponding to self.

A packed word on alphabet \(\{1,2,3,\ldots\}\) is any word whose maximum letter is the same as its total number of distinct letters. Let \(P\) be an ordered set partition of a set \(X\). The corresponding packed word \(w_1 w_2 \cdots w_n\) is constructed by having letter \(w_i = j\) if the \(i\)-th smallest entry in \(X\) occurs in the \(j\)-th block of \(P\).

See also

Word.to_ordered_set_partition()

Warning

This assumes there is a total order on the underlying set.

EXAMPLES:

sage: S = OrderedSetPartitions()
sage: x = S([[3,5], [2], [1,4,6]])
sage: x.to_packed_word()
word: 321313

sage: x = S([['a', 'c', 'e'], ['b', 'd']])
sage: x.to_packed_word()
word: 12121

>>> from sage.all import *
>>> S = OrderedSetPartitions()
>>> x = S([[Integer(3),Integer(5)], [Integer(2)], [Integer(1),Integer(4),Integer(6)]])
>>> x.to_packed_word()
word: 321313

>>> x = S([['a', 'c', 'e'], ['b', 'd']])
>>> x.to_packed_word()
word: 12121
class sage.combinat.set_partition_ordered.OrderedSetPartitions(s)[source]

Bases: UniqueRepresentation, Parent

Return the combinatorial class of ordered set partitions of s.

The optional argument c, if specified, restricts the parts of the partition to have certain sizes (the entries of c).

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().parent() is OS
True

>>> from sage.all import *
>>> OS = OrderedSetPartitions([Integer(1),Integer(2),Integer(3),Integer(4)]); OS
Ordered set partitions of {1, 2, 3, 4}
>>> OS.cardinality()
75
>>> OS.first()
[{1}, {2}, {3}, {4}]
>>> OS.last()
[{1, 2, 3, 4}]
>>> OS.random_element().parent() is OS
True


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}]]

>>> from sage.all import *
>>> OS = OrderedSetPartitions([Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(2),Integer(2)]); OS
Ordered set partitions of {1, 2, 3, 4} into parts of size [2, 2]
>>> OS.cardinality()
6
>>> OS.first()
[{1, 2}, {3, 4}]
>>> OS.last()
[{3, 4}, {1, 2}]
>>> 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")
sage: OS  # random
Ordered set partitions of {'a', 't', 'c'}
sage: sorted(OS.list(), key=str)
[[{'a', 'c', 't'}],
 [{'a', 'c'}, {'t'}],
 [{'a', 't'}, {'c'}],
 [{'a'}, {'c', 't'}],
 [{'a'}, {'c'}, {'t'}],
 [{'a'}, {'t'}, {'c'}],
 [{'c', 't'}, {'a'}],
 [{'c'}, {'a', 't'}],
 [{'c'}, {'a'}, {'t'}],
 [{'c'}, {'t'}, {'a'}],
 [{'t'}, {'a', 'c'}],
 [{'t'}, {'a'}, {'c'}],
 [{'t'}, {'c'}, {'a'}]]

>>> from sage.all import *
>>> OS = OrderedSetPartitions("cat")
>>> OS  # random
Ordered set partitions of {'a', 't', 'c'}
>>> sorted(OS.list(), key=str)
[[{'a', 'c', 't'}],
 [{'a', 'c'}, {'t'}],
 [{'a', 't'}, {'c'}],
 [{'a'}, {'c', 't'}],
 [{'a'}, {'c'}, {'t'}],
 [{'a'}, {'t'}, {'c'}],
 [{'c', 't'}, {'a'}],
 [{'c'}, {'a', 't'}],
 [{'c'}, {'a'}, {'t'}],
 [{'c'}, {'t'}, {'a'}],
 [{'t'}, {'a', 'c'}],
 [{'t'}, {'a'}, {'c'}],
 [{'t'}, {'c'}, {'a'}]]
Element[source]

alias of OrderedSetPartition

from_finite_word(w, check=True)[source]

Return the unique ordered set partition of \(\{1, 2, \ldots, n\}\) corresponding to a word \(w\) of length \(n\).

See also

Word.to_ordered_set_partition()

EXAMPLES:

sage: A = OrderedSetPartitions().from_finite_word('abcabcabd'); A
[{1, 4, 7}, {2, 5, 8}, {3, 6}, {9}]
sage: B = OrderedSetPartitions().from_finite_word([1,2,3,1,2,3,1,2,4])
sage: A == B
True

>>> from sage.all import *
>>> A = OrderedSetPartitions().from_finite_word('abcabcabd'); A
[{1, 4, 7}, {2, 5, 8}, {3, 6}, {9}]
>>> B = OrderedSetPartitions().from_finite_word([Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(4)])
>>> A == B
True
class sage.combinat.set_partition_ordered.OrderedSetPartitions_all[source]

Bases: OrderedSetPartitions

Ordered set partitions of \(\{1, \ldots, n\}\) for all \(n \in \ZZ_{\geq 0}\).

class Element(parent, s, check=True)[source]

Bases: OrderedSetPartition

subset(size=None, **kwargs)[source]

Return the subset of ordered set partitions of a given size and additional keyword arguments.

EXAMPLES:

sage: P = OrderedSetPartitions()
sage: P.subset(4)
Ordered set partitions of {1, 2, 3, 4}

>>> from sage.all import *
>>> P = OrderedSetPartitions()
>>> P.subset(Integer(4))
Ordered set partitions of {1, 2, 3, 4}
class sage.combinat.set_partition_ordered.OrderedSetPartitions_s(s)[source]

Bases: OrderedSetPartitions

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

cardinality()[source]

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

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(0)).cardinality()
1
>>> OrderedSetPartitions(Integer(1)).cardinality()
1
>>> OrderedSetPartitions(Integer(2)).cardinality()
3
>>> OrderedSetPartitions(Integer(3)).cardinality()
13
>>> OrderedSetPartitions([Integer(1),Integer(2),Integer(3)]).cardinality()
13
>>> OrderedSetPartitions(Integer(4)).cardinality()
75
>>> OrderedSetPartitions(Integer(5)).cardinality()
541
class sage.combinat.set_partition_ordered.OrderedSetPartitions_scomp(s, comp)[source]

Bases: OrderedSetPartitions

cardinality()[source]

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

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(5),[Integer(2),Integer(3)]).cardinality()
10
>>> OrderedSetPartitions(Integer(0), []).cardinality()
1
>>> OrderedSetPartitions(Integer(0), [Integer(0)]).cardinality()
1
>>> OrderedSetPartitions(Integer(0), [Integer(0),Integer(0)]).cardinality()
1
>>> OrderedSetPartitions(Integer(5), [Integer(2),Integer(0),Integer(3)]).cardinality()
10
class sage.combinat.set_partition_ordered.OrderedSetPartitions_sn(s, n)[source]

Bases: OrderedSetPartitions

cardinality()[source]

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

>>> from sage.all import *
>>> OrderedSetPartitions(Integer(4),Integer(2)).cardinality()
14
>>> OrderedSetPartitions(Integer(4),Integer(1)).cardinality()
1
class sage.combinat.set_partition_ordered.SplitNK(s, comp)[source]

Bases: OrderedSetPartitions_scomp

sage.combinat.set_partition_ordered.multiset_permutation_next_lex(l)[source]

Return the next multiset permutation after l.

EXAMPLES:

sage: from sage.combinat.set_partition_ordered import multiset_permutation_next_lex
sage: l = [0, 0, 1, 1, 2]
sage: while multiset_permutation_next_lex(l):
....:     print(l)
[0, 0, 1, 2, 1]
[0, 0, 2, 1, 1]
[0, 1, 0, 1, 2]
[0, 1, 0, 2, 1]
[0, 1, 1, 0, 2]
[0, 1, 1, 2, 0]
...
[1, 1, 2, 0, 0]
[1, 2, 0, 0, 1]
[1, 2, 0, 1, 0]
[1, 2, 1, 0, 0]
[2, 0, 0, 1, 1]
[2, 0, 1, 0, 1]
[2, 0, 1, 1, 0]
[2, 1, 0, 0, 1]
[2, 1, 0, 1, 0]
[2, 1, 1, 0, 0]

>>> from sage.all import *
>>> from sage.combinat.set_partition_ordered import multiset_permutation_next_lex
>>> l = [Integer(0), Integer(0), Integer(1), Integer(1), Integer(2)]
>>> while multiset_permutation_next_lex(l):
...     print(l)
[0, 0, 1, 2, 1]
[0, 0, 2, 1, 1]
[0, 1, 0, 1, 2]
[0, 1, 0, 2, 1]
[0, 1, 1, 0, 2]
[0, 1, 1, 2, 0]
...
[1, 1, 2, 0, 0]
[1, 2, 0, 0, 1]
[1, 2, 0, 1, 0]
[1, 2, 1, 0, 0]
[2, 0, 0, 1, 1]
[2, 0, 1, 0, 1]
[2, 0, 1, 1, 0]
[2, 1, 0, 0, 1]
[2, 1, 0, 1, 0]
[2, 1, 1, 0, 0]
sage.combinat.set_partition_ordered.multiset_permutation_to_ordered_set_partition(l, m)[source]

Convert a multiset permutation to an ordered set partition.

INPUT:

  • l – a multiset permutation

  • m – number of parts

EXAMPLES:

sage: from sage.combinat.set_partition_ordered import multiset_permutation_to_ordered_set_partition
sage: l = [0, 0, 1, 1, 2]
sage: multiset_permutation_to_ordered_set_partition(l, 3)
[[0, 1], [2, 3], [4]]

>>> from sage.all import *
>>> from sage.combinat.set_partition_ordered import multiset_permutation_to_ordered_set_partition
>>> l = [Integer(0), Integer(0), Integer(1), Integer(1), Integer(2)]
>>> multiset_permutation_to_ordered_set_partition(l, Integer(3))
[[0, 1], [2, 3], [4]]