Ordered Multiset Partitions into Sets and the Minimaj Crystal¶
This module provides element and parent classes for ordered multiset
partitions. It also implements the minimaj crystal of Benkart et al.
[BCHOPSY2017]. (See MinimajCrystal
.)
AUTHORS:
- Aaron Lauve (2018): initial implementation. First draft of minimaj crystal code provided by Anne Schilling.
REFERENCES:
EXAMPLES:
An ordered multiset partition into sets of the multiset \(\{\{1, 3, 3, 5\}\}\):
sage: OrderedMultisetPartitionIntoSets([[5, 3], [1, 3]])
[{3,5}, {1,3}]
Ordered multiset partitions into sets of the multiset \(\{\{1, 3, 3\}\}\):
sage: OrderedMultisetPartitionsIntoSets([1,1,3]).list()
[[{1}, {1}, {3}], [{1}, {1,3}], [{1}, {3}, {1}], [{1,3}, {1}], [{3}, {1}, {1}]]
Ordered multiset partitions into sets of the integer 4:
sage: OrderedMultisetPartitionsIntoSets(4).list()
[[{4}], [{1,3}], [{3}, {1}], [{1,2}, {1}], [{2}, {2}], [{2}, {1}, {1}],
[{1}, {3}], [{1}, {1,2}], [{1}, {2}, {1}], [{1}, {1}, {2}], [{1}, {1}, {1}, {1}]]
Ordered multiset partitions into sets on the alphabet \(\{1, 4\}\) of order 3:
sage: OrderedMultisetPartitionsIntoSets([1,4], 3).list()
[[{1,4}, {1}], [{1,4}, {4}], [{1}, {1,4}], [{4}, {1,4}], [{1}, {1}, {1}],
[{1}, {1}, {4}], [{1}, {4}, {1}], [{1}, {4}, {4}], [{4}, {1}, {1}],
[{4}, {1}, {4}], [{4}, {4}, {1}], [{4}, {4}, {4}]]
Crystal of ordered multiset partitions into sets on the alphabet \(\{1,2,3\}\) with 4 letters divided into 2 blocks:
sage: crystals.Minimaj(3, 4, 2).list()
[((2, 3, 1), (1,)), ((2, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (1, 2)),
((3, 1), (1, 2)), ((3, 1, 2), (2,)), ((3, 1), (1, 3)), ((3, 1), (2, 3)),
((3, 2), (2, 3)), ((2, 1), (1, 3)), ((2,), (1, 2, 3)), ((3,), (1, 2, 3)),
((1,), (1, 2, 3)), ((1, 2), (2, 3)), ((1, 2, 3), (3,))]
-
sage.combinat.multiset_partition_into_sets_ordered.
MinimajCrystal
¶ Crystal of ordered multiset partitions into sets with \(ell\) letters from alphabet \(\{1, 2, \ldots, n\}\) divided into \(k\) blocks.
Elements are represented in the minimaj ordering of blocks as in Benkart et al. [BCHOPSY2017].
Note
Elements are not stored internally as ordered multiset partitions into sets, but as certain (pairs of) words stemming from the minimaj bijection \(\phi\) of [BCHOPSY2017]. See
sage.combinat.multiset_partition_into_sets_ordered.MinimajCrystal.Element
for further details.AUTHORS:
- Anne Schilling (2018): initial draft
- Aaron Lauve (2018): changed to use
Letters
crystal for elements
EXAMPLES:
sage: list(crystals.Minimaj(2,3,2)) [((2, 1), (1,)), ((2,), (1, 2)), ((1,), (1, 2)), ((1, 2), (2,))] sage: b = crystals.Minimaj(3, 5, 2).an_element(); b ((2, 3, 1), (1, 2)) sage: b.f(2) ((2, 3, 1), (1, 3)) sage: b.e(2)
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionIntoSets
¶ Ordered Multiset Partition into sets
An ordered multiset partition into sets \(c\) of a multiset \(X\) is a list \([c_1, \ldots, c_r]\) of nonempty subsets of \(X\) (note: not sub-multisets), called the blocks of \(c\), whose multi-union is \(X\).
EXAMPLES:
The simplest way to create an ordered multiset partition into sets is by specifying its blocks as a list or tuple:
sage: OrderedMultisetPartitionIntoSets([[3],[2,1]]) [{3}, {1,2}] sage: OrderedMultisetPartitionIntoSets(((3,), (1,2))) [{3}, {1,2}] sage: OrderedMultisetPartitionIntoSets([set([i]) for i in range(2,5)]) [{2}, {3}, {4}]
REFERENCES:
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets
¶ Ordered Multiset Partitions into Sets.
An ordered multiset partition into sets \(c\) of a multiset \(X\) is a list of nonempty subsets (not multisets), called the blocks of \(c\), whose multi-union is \(X\).
The number of blocks of \(c\) is called its length. The order of \(c\) is the cardinality of the multiset \(X\). If, additionally, \(X\) is a multiset of positive integers, then the size of \(c\) is the sum of all elements of \(X\).
The user may wish to focus on ordered multiset partitions into sets of a given size, or over a given alphabet. Hence, this class allows a variety of arguments as input.
INPUT:
Expects one or two arguments, with different behaviors resulting:
- One Argument:
- \(X\) – a dictionary or list or tuple (representing a multiset for \(c\)), or an integer (representing the size of \(c\))
- Two Arguments:
- \(A\) – a list (representing allowable letters within blocks of \(c\)), or a positive integer (representing the maximal allowable letter)
- \(n\) – a nonnegative integer (the total number of letters within \(c\))
Optional keyword arguments are as follows: (See corresponding methods in see
OrderedMultisetPartitionIntoSets
for more details.)weight=X
(list or dictionary \(X\)) specifies the multiset for \(c\)size=n
(integer \(n\)) specifies the size of \(c\)alphabet=A
(iterable \(A\)) specifies allowable elements for the blocks of \(c\)length=k
(integer \(k\)) specifies the number of blocks in the partitionmin_length=k
(integer \(k\)) specifies minimum number of blocks in the partitionmax_length=k
(integer \(k\)) specifies maximum number of blocks in the partitionorder=n
(integer \(n\)) specifies the cardinality of the multiset that \(c\) partitionsmin_order=n
(integer \(n\)) specifies minimum number of elements in the partitionmax_order=n
(integer \(n\)) specifies maximum number of elements in the partition
EXAMPLES:
Passing one argument to
OrderedMultisetPartitionsIntoSets
:There are 5 ordered multiset partitions into sets of the multiset \(\{\{1, 1, 4\}\}\):
sage: OrderedMultisetPartitionsIntoSets([1,1,4]).cardinality() 5
Here is the list of them:
sage: OrderedMultisetPartitionsIntoSets([1,1,4]).list() [[{1}, {1}, {4}], [{1}, {1,4}], [{1}, {4}, {1}], [{1,4}, {1}], [{4}, {1}, {1}]]
By chance, there are also 5 ordered multiset partitions into sets of the integer 3:
sage: OrderedMultisetPartitionsIntoSets(3).cardinality() 5
Here is the list of them:
sage: OrderedMultisetPartitionsIntoSets(3).list() [[{3}], [{1,2}], [{2}, {1}], [{1}, {2}], [{1}, {1}, {1}]]
Passing two arguments to
OrderedMultisetPartitionsIntoSets
:There are also 5 ordered multiset partitions into sets of order 2 over the alphabet \(\{1, 4\}\):
sage: OrderedMultisetPartitionsIntoSets([1, 4], 2) Ordered Multiset Partitions into Sets of order 2 over alphabet {1, 4} sage: OrderedMultisetPartitionsIntoSets([1, 4], 2).cardinality() 5
Here is the list of them:
sage: OrderedMultisetPartitionsIntoSets([1, 4], 2).list() [[{1,4}], [{1}, {1}], [{1}, {4}], [{4}, {1}], [{4}, {4}]]
If no arguments are passed to
OrderedMultisetPartitionsIntoSets
, then the code returns all ordered multiset partitions into sets:sage: OrderedMultisetPartitionsIntoSets() Ordered Multiset Partitions into Sets sage: [] in OrderedMultisetPartitionsIntoSets() True sage: [[2,3], [1]] in OrderedMultisetPartitionsIntoSets() True sage: [['a','b'], ['a']] in OrderedMultisetPartitionsIntoSets() True sage: [[-2,3], [3]] in OrderedMultisetPartitionsIntoSets() True sage: [[2], [3,3]] in OrderedMultisetPartitionsIntoSets() False
The following examples show how to test whether or not an object is an ordered multiset partition into sets:
sage: [[3,2],[2]] in OrderedMultisetPartitionsIntoSets() True sage: [[3,2],[2]] in OrderedMultisetPartitionsIntoSets(7) True sage: [[3,2],[2]] in OrderedMultisetPartitionsIntoSets([2,2,3]) True sage: [[3,2],[2]] in OrderedMultisetPartitionsIntoSets(5) False
Optional keyword arguments
Passing keyword arguments that are incompatible with required requirements results in an error; otherwise, the collection of ordered multiset partitions into sets is restricted accordingly:
The
weight
keyword:This is used to specify which multiset \(X\) is to be considered, if this multiset was not passed as one of the required arguments for
OrderedMultisetPartitionsIntoSets
. In principle, it is a dictionary, but weak compositions are also allowed. For example, the ordered multiset partitions into sets of integer 4 are listed by weight below:sage: OrderedMultisetPartitionsIntoSets(4, weight=[0,0,0,1]) Ordered Multiset Partitions into Sets of integer 4 with constraint: weight={4: 1} sage: OrderedMultisetPartitionsIntoSets(4, weight=[0,0,0,1]).list() [[{4}]] sage: OrderedMultisetPartitionsIntoSets(4, weight=[1,0,1]).list() [[{1}, {3}], [{1,3}], [{3}, {1}]] sage: OrderedMultisetPartitionsIntoSets(4, weight=[0,2]).list() [[{2}, {2}]] sage: OrderedMultisetPartitionsIntoSets(4, weight=[0,1,1]).list() [] sage: OrderedMultisetPartitionsIntoSets(4, weight=[2,1]).list() [[{1}, {1}, {2}], [{1}, {1,2}], [{1}, {2}, {1}], [{1,2}, {1}], [{2}, {1}, {1}]] sage: O1 = OrderedMultisetPartitionsIntoSets(weight=[2,0,1]) sage: O2 = OrderedMultisetPartitionsIntoSets(weight={1:2, 3:1}) sage: O1 == O2 True sage: OrderedMultisetPartitionsIntoSets(4, weight=[4]).list() [[{1}, {1}, {1}, {1}]]
The
size
keyword:This is used to constrain the sum of entries across all blocks of the ordered multiset partition into sets. (This size is not pre-determined when alphabet \(A\) and order \(d\) are passed as required arguments.) For example, the ordered multiset partitions into sets of order 3 over the alphabet \([1,2,4]\) that have size equal to 5 are as follows:
sage: OMPs = OrderedMultisetPartitionsIntoSets sage: OMPs([1,2,4], 3, size=5).list() [[{1,2}, {2}], [{2}, {1,2}], [{2}, {2}, {1}], [{2}, {1}, {2}], [{1}, {2}, {2}]]
The
alphabet
option:This is used to constrain which integers appear across all blocks of the ordered multiset partition into sets. For example, the ordered multiset partitions into sets of integer 4 are listed for different choices of alphabet below. Note that
alphabet
is allowed to be an integer or an iterable:sage: OMPs = OrderedMultisetPartitionsIntoSets sage: OMPs(4, alphabet=3).list() [[{1,3}], [{3}, {1}], [{1,2}, {1}], [{2}, {2}], [{2}, {1}, {1}], [{1}, {3}], [{1}, {1,2}], [{1}, {2}, {1}], [{1}, {1}, {2}], [{1}, {1}, {1}, {1}]] sage: OMPs(4, alphabet=3) == OMPs(4, alphabet=[1,2,3]) True sage: OMPs(4, alphabet=[3]).list() [] sage: OMPs(4, alphabet=[1,3]).list() [[{1,3}], [{3}, {1}], [{1}, {3}], [{1}, {1}, {1}, {1}]] sage: OMPs(4, alphabet=[2]).list() [[{2}, {2}]] sage: OMPs(4, alphabet=[1,2]).list() [[{1,2}, {1}], [{2}, {2}], [{2}, {1}, {1}], [{1}, {1,2}], [{1}, {2}, {1}], [{1}, {1}, {2}], [{1}, {1}, {1}, {1}]] sage: OMPs(4, alphabet=4).list() == OMPs(4).list() True
The
length
,min_length
, andmax_length
options:These are used to constrain the number of blocks within the ordered multiset partitions into sets. For example, the ordered multiset partitions into sets of integer 4 of length exactly 2, at least 2, and at most 2 are given by:
sage: OrderedMultisetPartitionsIntoSets(4, length=2).list() [[{3}, {1}], [{1,2}, {1}], [{2}, {2}], [{1}, {3}], [{1}, {1,2}]] sage: OrderedMultisetPartitionsIntoSets(4, min_length=3).list() [[{2}, {1}, {1}], [{1}, {2}, {1}], [{1}, {1}, {2}], [{1}, {1}, {1}, {1}]] sage: OrderedMultisetPartitionsIntoSets(4, max_length=2).list() [[{4}], [{1,3}], [{3}, {1}], [{1,2}, {1}], [{2}, {2}], [{1}, {3}], [{1}, {1,2}]]
The
order
,min_order
, andmax_order
options:These are used to constrain the number of elements across all blocks of the ordered multiset partitions into sets. For example, the ordered multiset partitions into sets of integer 4 are listed by order below:
sage: OrderedMultisetPartitionsIntoSets(4, order=1).list() [[{4}]] sage: OrderedMultisetPartitionsIntoSets(4, order=2).list() [[{1,3}], [{3}, {1}], [{2}, {2}], [{1}, {3}]] sage: OrderedMultisetPartitionsIntoSets(4, order=3).list() [[{1,2}, {1}], [{2}, {1}, {1}], [{1}, {1,2}], [{1}, {2}, {1}], [{1}, {1}, {2}]] sage: OrderedMultisetPartitionsIntoSets(4, order=4).list() [[{1}, {1}, {1}, {1}]]
Also, here is a use of
max_order
, giving the ordered multiset partitions into sets of integer 4 with order 1 or 2:sage: OrderedMultisetPartitionsIntoSets(4, max_order=2).list() [[{4}], [{1,3}], [{3}, {1}], [{2}, {2}], [{1}, {3}]]
- One Argument:
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_X
¶ Class of ordered multiset partitions into sets of a fixed multiset \(X\).
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_X_constraints
¶ Class of ordered multiset partitions into sets of a fixed multiset \(X\) satisfying constraints.
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_all_constraints
¶ All ordered multiset partitions into sets (with or without constraints).
EXAMPLES:
sage: C = OrderedMultisetPartitionsIntoSets(); C Ordered Multiset Partitions into Sets sage: [[1],[1,'a']] in C True sage: OrderedMultisetPartitionsIntoSets(weight=[2,0,1], length=2) Ordered Multiset Partitions into Sets of multiset {{1, 1, 3}} with constraint: length=2
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_alph_d
¶ Class of ordered multiset partitions into sets of specified order \(d\) over a fixed alphabet \(A\).
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_alph_d_constraints
¶ Class of ordered multiset partitions into sets of specified order \(d\) over a fixed alphabet \(A\) satisfying constraints.
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_n
¶ Ordered multiset partitions into sets of a fixed integer \(n\).
-
sage.combinat.multiset_partition_into_sets_ordered.
OrderedMultisetPartitionsIntoSets_n_constraints
¶ Class of ordered multiset partitions into sets of a fixed integer \(n\) satisfying constraints.