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 partition
  • min_length=k (integer \(k\)) specifies minimum number of blocks in the partition
  • max_length=k (integer \(k\)) specifies maximum number of blocks in the partition
  • order=n (integer \(n\)) specifies the cardinality of the multiset that \(c\) partitions
  • min_order=n (integer \(n\)) specifies minimum number of elements in the partition
  • max_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, and max_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, and max_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}]]
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.