Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Partition tuples
A :class:`PartitionTuple` is a tuple of partitions. That is, an ordered `k`-tuple of partitions `\mu=(\mu^{(1)},\mu^{(2)},...,\mu^{(k)})`. If
.. MATH::
n = \lvert \mu \rvert = \lvert \mu^{(1)} \rvert + \lvert \mu^{(2)} \rvert + \cdots + \lvert \mu^{(k)} \rvert
then we say that `\mu` is a `k`-partition of `n`.
In representation theory partition tuples arise as the natural indexing set for the ordinary irreducible representations of:
- the wreath products of cyclic groups with symmetric groups, - the Ariki-Koike algebras, or the cyclotomic Hecke algebras of the complex reflection groups of type `G(r,1,n)`, - the degenerate cyclotomic Hecke algebras of type `G(r,1,n)`.
When these algebras are not semisimple, partition tuples index an important class of modules for the algebras, which are generalisations of the Specht modules of the symmetric groups.
Tuples of partitions also index the standard basis of the higher level combinatorial Fock spaces. As a consequence, the combinatorics of partition tuples encapsulates the canonical bases of crystal graphs for the irreducible integrable highest weight modules of the (quantized) affine special linear groups and the (quantized) affine general linear groups. By the categorification theorems of Ariki, Varagnolo-Vasserot, Stroppel-Webster and others, in characteristic zero the degenerate and non-degenerate cyclotomic Hecke algebras, via their Khovanov-Lauda-Rouquier grading, categorify the canonical bases of the quantum affine special and general linear groups.
Partitions are naturally in bijection with 1-tuples of partitions. Most of the combinatorial operations defined on partitions extend to partition tuples in a meaningful way. For example, the semisimple branching rules for the Specht modules are described by adding and removing cells from partition tuples and the modular branching rules correspond to adding and removing good and cogood nodes, which is the underlying combinatorics for the associated crystal graphs.
A :class:`PartitionTuple` belongs to :class:`PartitionTuples` and its derived classes. :class:`PartitionTuples` is the parent class for all partitions tuples. Four different classes of tuples of partitions are currently supported:
- ``PartitionTuples(level=k,size=n)`` are `k`-tuple of partitions of `n`. - ``PartitionTuples(level=k)`` are `k`-tuple of partitions. - ``PartitionTuples(size=n)`` are tuples of partitions of `n`. - ``PartitionTuples()`` are tuples of partitions.
.. NOTE::
As with :class:`Partitions`, in sage the cells, or nodes, of partition tuples are 0-based. For example, the (lexicographically) first cell in any non-empty partition tuple is `[0,0,0]`.
EXAMPLES::
sage: PartitionTuple([[2,2],[1,1],[2]]).cells() [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (2, 0, 0), (2, 0, 1)]
.. NOTE::
Many :class:`PartitionTuple` methods take the individual coordinates `(k,r,c)` as their arguments, here `k` is the component, `r` is the row index and `c` is the column index. If your coordinates are in the form ``(k,r,c)`` then use Python's \*-operator.
EXAMPLES::
sage: mu=PartitionTuple([[1,1],[2],[2,1]]) sage: [ mu.arm_length(*c) for c in mu.cells()] [0, 0, 1, 0, 1, 0, 0]
.. WARNING::
In sage, if ``mu`` is a partition tuple then ``mu[k]`` most naturally refers to the `k`-th component of ``mu``, so we use the convention of the `(k,r,c)`-th cell in a partition tuple refers to the cell in component `k`, row `r`, and column `c`. In the literature, the cells of a partition tuple are usually written in the form `(r,c,k)`, where `r` is the row index, `c` is the column index, and `k` is the component index.
REFERENCES:
.. [DJM99] \R. Dipper, G. James and A. Mathas "The cyclotomic q-Schur algebra", Math. Z, 229 (1999), 385-416. .. [BK09] \J. Brundan and A. Kleshchev "Graded decomposition numbers for cyclotomic Hecke algebras", Adv. Math., 222 (2009), 1883-1942"
AUTHORS:
- Andrew Mathas (2012-06-01): Initial classes.
EXAMPLES:
First is a finite enumerated set and the remaining classes are infinite enumerated sets::
sage: PartitionTuples().an_element() ([1, 1, 1, 1], [2, 1, 1], [3, 1], [4]) sage: PartitionTuples(4).an_element() ([], [1], [2], [3]) sage: PartitionTuples(size=5).an_element() ([1], [1], [1], [1], [1]) sage: PartitionTuples(4,5).an_element() ([1], [], [], [4]) sage: PartitionTuples(3,2)[:] [([2], [], []), ([1, 1], [], []), ([1], [1], []), ([1], [], [1]), ([], [2], []), ([], [1, 1], []), ([], [1], [1]), ([], [], [2]), ([], [], [1, 1])] sage: PartitionTuples(2,3).list() [([3], []), ([2, 1], []), ([1, 1, 1], []), ([2], [1]), ([1, 1], [1]), ([1], [2]), ([1], [1, 1]), ([], [3]), ([], [2, 1]), ([], [1, 1, 1])]
One tuples of partitions are naturally in bijection with partitions and, as far as possible, partition tuples attempts to identify one tuples with partitions::
sage: Partition([4,3]) == PartitionTuple([[4,3]]) True sage: Partition([4,3]) == PartitionTuple([4,3]) True sage: PartitionTuple([4,3]) [4, 3] sage: Partition([4,3]) in PartitionTuples() True
Partition tuples come equipped with many of the corresponding methods for partitions. For example, it is possible to add and remove cells, to conjugate partition tuples, to work with their diagrams, compare partition tuples in dominance and so::
sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).pp() **** - ** *** * ** * sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).conjugate() ([1, 1, 1], [3, 2], [], [2, 1, 1, 1]) sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).conjugate().pp() * *** - ** * ** * * * * sage: lam=PartitionTuples(3)([[3,2],[],[1,1,1,1]]); lam ([3, 2], [], [1, 1, 1, 1]) sage: lam.level() 3 sage: lam.size() 9 sage: lam.category() Category of elements of Partition tuples of level 3 sage: lam.parent() Partition tuples of level 3 sage: lam[0] [3, 2] sage: lam[1] [] sage: lam[2] [1, 1, 1, 1] sage: lam.pp() *** - * ** * * * sage: lam.removable_cells() [(0, 0, 2), (0, 1, 1), (2, 3, 0)] sage: lam.down_list() [([2, 2], [], [1, 1, 1, 1]), ([3, 1], [], [1, 1, 1, 1]), ([3, 2], [], [1, 1, 1])] sage: lam.addable_cells() [(0, 0, 3), (0, 1, 2), (0, 2, 0), (1, 0, 0), (2, 0, 1), (2, 4, 0)] sage: lam.up_list() [([4, 2], [], [1, 1, 1, 1]), ([3, 3], [], [1, 1, 1, 1]), ([3, 2, 1], [], [1, 1, 1, 1]), ([3, 2], [1], [1, 1, 1, 1]), ([3, 2], [], [2, 1, 1, 1]), ([3, 2], [], [1, 1, 1, 1, 1])] sage: lam.conjugate() ([4], [], [2, 2, 1]) sage: lam.dominates( PartitionTuple([[3],[1],[2,2,1]]) ) False sage: lam.dominates( PartitionTuple([[3],[2],[1,1,1]])) True
Every partition tuple behaves every much like a tuple of partitions::
sage: mu=PartitionTuple([[4,1],[],[2,2,1],[3]]) sage: [ nu for nu in mu ] [[4, 1], [], [2, 2, 1], [3]] sage: Set([ type(nu) for nu in mu ]) {<class 'sage.combinat.partition.Partitions_all_with_category.element_class'>} sage: mu[2][2] 1 sage: mu[3] [3] sage: mu.components() [[4, 1], [], [2, 2, 1], [3]] sage: mu.components() == [ nu for nu in mu ] True sage: mu[0] [4, 1] sage: mu[1] [] sage: mu[2] [2, 2, 1] sage: mu[2][0] 2 sage: mu[2][1] 2 sage: mu.level() 4 sage: len(mu) 4 sage: mu.cells() [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (2, 2, 0), (3, 0, 0), (3, 0, 1), (3, 0, 2)] sage: mu.addable_cells() [(0, 0, 4), (0, 1, 1), (0, 2, 0), (1, 0, 0), (2, 0, 2), (2, 2, 1), (2, 3, 0), (3, 0, 3), (3, 1, 0)] sage: mu.removable_cells() [(0, 0, 3), (0, 1, 0), (2, 1, 1), (2, 2, 0), (3, 0, 2)]
Attached to a partition tuple is the corresponding Young, or parabolic, subgroup::
sage: mu.young_subgroup() Permutation Group with generators [(), (12,13), (11,12), (8,9), (6,7), (3,4), (2,3), (1,2)] sage: mu.young_subgroup_generators() [1, 2, 3, 6, 8, 11, 12]
"""
#***************************************************************************** # Copyright (C) 2012 Andrew Mathas <andrew.mathas@sydney.edu.au> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function, absolute_import
from six.moves import range
import itertools
from .combinat import CombinatorialElement from .integer_vector import IntegerVectors from .partition import (Partition, Partitions, Partitions_n, _Partitions, RegularPartitions_all, RegularPartitions_n) from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets from sage.groups.perm_gps.permgroup import PermutationGroup from sage.interfaces.all import gp from sage.misc.cachefunc import cached_method from sage.rings.all import NN, ZZ, IntegerModRing from sage.rings.integer import Integer from sage.sets.positive_integers import PositiveIntegers from sage.structure.parent import Parent from sage.structure.unique_representation import UniqueRepresentation
#-------------------------------------------------- # Partition tuple - element class #-------------------------------------------------- class PartitionTuple(CombinatorialElement): r""" A tuple of :class:`Partition`.
A tuple of partition comes equipped with many of methods available to partitions. The ``level`` of the PartitionTuple is the length of the tuple.
This is an ordered `k`-tuple of partitions `\mu=(\mu^{(1)},\mu^{(2)},...,\mu^{(k)})`. If
.. MATH::
n = \lvert \mu \rvert = \lvert \mu^{(1)} \rvert + \lvert \mu^{(2)} \rvert + \cdots + \lvert \mu^{(k)} \rvert
then `\mu` is a `k`-partition of `n`.
In representation theory PartitionTuples arise as the natural indexing set for the ordinary irreducible representations of:
- the wreath products of cyclic groups with symmetric groups - the Ariki-Koike algebras, or the cyclotomic Hecke algebras of the complex reflection groups of type `G(r,1,n)` - the degenerate cyclotomic Hecke algebras of type `G(r,1,n)`
When these algebras are not semisimple, partition tuples index an important class of modules for the algebras which are generalisations of the Specht modules of the symmetric groups.
Tuples of partitions also index the standard basis of the higher level combinatorial Fock spaces. As a consequence, the combinatorics of partition tuples encapsulates the canonical bases of crystal graphs for the irreducible integrable highest weight modules of the (quantized) affine special linear groups and the (quantized) affine general linear groups. By the categorification theorems of Ariki, Varagnolo-Vasserot, Stroppel-Webster and others, in characteristic zero the degenerate and non-degenerate cyclotomic Hecke algebras, via their Khovanov-Lauda-Rouquier grading, categorify the canonical bases of the quantum affine special and general linear groups.
Partitions are naturally in bijection with 1-tuples of partitions. Most of the combinatorial operations defined on partitions extend to PartitionTuples in a meaningful way. For example, the semisimple branching rules for the Specht modules are described by adding and removing cells from partition tuples and the modular branching rules correspond to adding and removing good and cogood nodes, which is the underlying combinatorics for the associated crystal graphs.
.. WARNING::
In the literature, the cells of a partition tuple are usually written in the form `(r,c,k)`, where `r` is the row index, `c` is the column index, and `k` is the component index. In sage, if ``mu`` is a partition tuple then ``mu[k]`` most naturally refers to the `k`-th component of ``mu``, so we use the convention of the `(k,r,c)`-th cell in a partition tuple refers to the cell in component `k`, row `r`, and column `c`.
INPUT:
Anything which can reasonably be interpreted as a tuple of partitions. That is, a list or tuple of partitions or valid input to :class:`Partition`.
EXAMPLES::
sage: mu=PartitionTuple( [[3,2],[2,1],[],[1,1,1,1]] ); mu ([3, 2], [2, 1], [], [1, 1, 1, 1]) sage: nu=PartitionTuple( ([3,2],[2,1],[],[1,1,1,1]) ); nu ([3, 2], [2, 1], [], [1, 1, 1, 1]) sage: mu == nu True sage: mu is nu False sage: mu in PartitionTuples() True sage: mu.parent() Partition tuples
sage: lam=PartitionTuples(3)([[3,2],[],[1,1,1,1]]); lam ([3, 2], [], [1, 1, 1, 1]) sage: lam.level() 3 sage: lam.size() 9 sage: lam.category() Category of elements of Partition tuples of level 3 sage: lam.parent() Partition tuples of level 3 sage: lam[0] [3, 2] sage: lam[1] [] sage: lam[2] [1, 1, 1, 1] sage: lam.pp() *** - * ** * * * sage: lam.removable_cells() [(0, 0, 2), (0, 1, 1), (2, 3, 0)] sage: lam.down_list() [([2, 2], [], [1, 1, 1, 1]), ([3, 1], [], [1, 1, 1, 1]), ([3, 2], [], [1, 1, 1])] sage: lam.addable_cells() [(0, 0, 3), (0, 1, 2), (0, 2, 0), (1, 0, 0), (2, 0, 1), (2, 4, 0)] sage: lam.up_list() [([4, 2], [], [1, 1, 1, 1]), ([3, 3], [], [1, 1, 1, 1]), ([3, 2, 1], [], [1, 1, 1, 1]), ([3, 2], [1], [1, 1, 1, 1]), ([3, 2], [], [2, 1, 1, 1]), ([3, 2], [], [1, 1, 1, 1, 1])] sage: lam.conjugate() ([4], [], [2, 2, 1]) sage: lam.dominates( PartitionTuple([[3],[1],[2,2,1]]) ) False sage: lam.dominates( PartitionTuple([[3],[2],[1,1,1]])) True
TESTS::
sage: TestSuite( PartitionTuple([4,3,2]) ).run() sage: TestSuite( PartitionTuple([[4,3,2],[],[],[3,2,1]]) ).run()
.. SEEALSO::
- :class:`PartitionTuples` - :class:`Partitions` """ Element = Partition
@staticmethod def __classcall_private__(self, mu): """ This delegates the construction of a :class:`PartitionTuple` to the ``element_class()`` call of the appropriate :class:`PartitionTuples_level`.
TESTS::
sage: mu=PartitionTuple([[1,1],[1]]) sage: mu.category() Category of elements of Partition tuples sage: type(mu) <class 'sage.combinat.partition_tuple.PartitionTuples_all_with_category.element_class'> """
# one way or another these two cases need to be treated separately
# We must check mu is a list of partitions
else:
def __init__(self, parent, mu): """ Initialize ``self`` and checks that the input determines a tuple of partitions.
EXAMPLES::
sage: PartitionTuple([]) [] sage: P = PartitionTuple([[2,1,1,0],[2,1]]); P ([2, 1, 1], [2, 1]) sage: TestSuite(P).run() sage: PartitionTuple([[],[],[2,1,2,1]]) Traceback (most recent call last): ... ValueError: [[], [], [2, 1, 2, 1]] is not a tuple of Partitions
"""
def level(self): """ Return the level of this partition tuple.
The level is the length of the tuple.
EXAMPLES::
sage: PartitionTuple([[2,1,1,0],[2,1]]).level() 2 sage: PartitionTuple([[],[],[2,1,1]]).level() 3 """
def __len__(self): """ Return the length of this partition tuple.
The length is also known as the level.
EXAMPLES::
sage: len( PartitionTuple([[2,1],[3,2],[1,1,1]]) ) 3
"""
def _repr_(self, compact=None): """ Return a string representation of ``self`` depending on :meth:`PartitionTuples.options`.
EXAMPLES::
sage: mu=PartitionTuple(([2,1],[3,2],[1,1,1])) # indirect doctest
sage: PartitionTuples.options(display="list"); mu ([2, 1], [3, 2], [1, 1, 1]) sage: PartitionTuples.options(display="diagram"); mu ** *** * * ** * * sage: PartitionTuples.options(display="compact_low"); mu 1,2|2,3|1^3 sage: PartitionTuples.options(display="compact_high"); mu 2,1|3,2|1^3 sage: PartitionTuples.options(display="exp_low"); mu 1, 2 | 2, 3 | 1^3 sage: PartitionTuples.options(display="exp_high"); mu 2, 1 | 3, 2 | 1^3 sage: PartitionTuples.options._reset()
sage: Partitions.options(convention="French"); sage: PartitionTuples.options(display="diagram"); mu * * ** * ** *** * sage: PartitionTuples.options(display="list"); mu ([2, 1], [3, 2], [1, 1, 1]) sage: PartitionTuples.options(display="compact_low"); mu 1,2|2,3|1^3 sage: PartitionTuples.options(display="compact_high"); mu 2,1|3,2|1^3 sage: PartitionTuples.options(display="exp_low"); mu 1, 2 | 2, 3 | 1^3 sage: PartitionTuples.options(display="exp_high"); mu 2, 1 | 3, 2 | 1^3 sage: PartitionTuples.options._reset() """
def _repr_diagram(self): """ Return a string representation of ``self`` as a Ferrers diagram.
EXAMPLES::
sage: print(PartitionTuple(([2,1],[3,2],[1,1,1]))._repr_diagram()) ** *** * * ** * * """
def _repr_list(self): """ Return a string representation of ``self`` as a list.
EXAMPLES::
sage: PartitionTuple(([2,1],[3,2],[1,1,1]))._repr_list() '([2, 1], [3, 2], [1, 1, 1])' """
def _repr_exp_low(self): """ Return a string representation of ``self`` in compact form (exponential form with highest first).
EXAMPLES::
sage: PartitionTuple(([2,1],[3,2],[1,1,1]))._repr_exp_low() '1, 2 | 2, 3 | 1^3' sage: PartitionTuple(([],[3,2],[1,1,1]))._repr_exp_low() '- | 2, 3 | 1^3' """
def _repr_exp_high(self): """ Return a string representation of ``self`` in compact form (exponential form with highest first).
EXAMPLES::
sage: PartitionTuple(([2,1],[3,2],[1,1,1,1,1,1,1,1,1,1]))._repr_exp_high() '2, 1 | 3, 2 | 1^10' sage: PartitionTuple(([],[3,2],[1,1,1]))._repr_exp_high() '- | 3, 2 | 1^3' """
def _repr_compact_low(self): """ Return a string representation of ``self`` in compact form (exponential form with highest first).
EXAMPLES::
sage: PartitionTuple(([2,1],[3,2],[1,1,1]))._repr_compact_low() '1,2|2,3|1^3' sage: PartitionTuple(([],[3,2],[1,1,1]))._repr_compact_low() '-|2,3|1^3' """
def _repr_compact_high(self): """ Return a string representation of ``self`` in compact form (exponential form with highest first).
EXAMPLES::
sage: PartitionTuple(([2,1],[3,2],[1,1,1]))._repr_compact_high() '2,1|3,2|1^3' sage: PartitionTuple(([],[3,2],[1,1,1]))._repr_compact_high() '-|3,2|1^3' """
# override default string representation which is str(self._list)
def _latex_(self): r""" Returns a LaTeX version of ``self``.
For more on the latex options, see :meth:`Partitions.option`.
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1]]) sage: PartitionTuples.options(latex='diagram'); latex(mu) # indirect doctest {\def\lr#1{\multicolumn{1}{@{\hspace{.6ex}}c@{\hspace{.6ex}}}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\\ \lr{\ast}&\lr{\ast}\\ \lr{\ast}\\ \end{array}$},\raisebox{-.6ex}{$\begin{array}[b]{*{1}c}\\ \lr{\ast}\\ \lr{\ast}\\ \lr{\ast}\\ \end{array}$} } sage: PartitionTuples.options(latex='exp_high'); latex(mu) # indirect doctest (2,1|1^{3}) sage: PartitionTuples.options(latex='exp_low'); latex(mu) # indirect doctest (1,2|1^{3}) sage: PartitionTuples.options(latex='list'); latex(mu) # indirect doctest [[2, 1], [1, 1, 1]] sage: PartitionTuples.options(latex='young_diagram'); latex(mu) # indirect doctest {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \lr{\phantom{x}}\\\cline{1-1} \end{array}$},\raisebox{-.6ex}{$\begin{array}[b]{*{1}c}\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} }
sage: PartitionTuples.options(latex="young_diagram", convention="french") sage: PartitionTuples.options(latex='exp_high'); latex(mu) # indirect doctest (2,1|1^{3}) sage: PartitionTuples.options(latex='exp_low'); latex(mu) # indirect doctest (1,2|1^{3}) sage: PartitionTuples.options(latex='list'); latex(mu) # indirect doctest [[2, 1], [1, 1, 1]] sage: PartitionTuples.options(latex='young_diagram'); latex(mu) # indirect doctest {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[t]{*{2}c}\cline{1-1} \lr{\phantom{x}}\\\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \end{array}$},\raisebox{-.6ex}{$\begin{array}[t]{*{1}c}\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} }
sage: PartitionTuples.options._reset() """
def _latex_young_diagram(self): """ LaTeX output as a Young diagram.
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1]])._latex_young_diagram() """
def _latex_diagram(self): """ LaTeX output as a Ferrers' diagram.
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1]])._latex_diagram() """
def _latex_list(self): """ LaTeX output as a list.
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1]])._latex_list() """
def _latex_exp_low(self): """ LaTeX output in exponential notation (lowest first).
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1,1,1,1,1,1,1,1]])._latex_exp_low() """ for (a,e) in enumerate(mu)) for mu in self.to_exp())
def _latex_exp_high(self): """ LaTeX output in exponential notation (highest first).
EXAMPLES::
sage: mu = PartitionTuple([[2, 1],[1,1,1,1,1,1,1,1,1,1]])._latex_exp_high() """ for (a,e) in enumerate(mu)][::-1]) for mu in self.to_exp())
def components(self): r""" Return a list containing the shape of this partition.
This function exists in order to give a uniform way of iterating over the \"components\" of partition tuples of level 1 (partitions) and for higher levels.
EXAMPLES::
sage: for t in PartitionTuple([[2,1],[3,2],[3]]).components(): ....: print('%s\n' % t.ferrers_diagram()) ... ** * <BLANKLINE> *** ** <BLANKLINE> *** <BLANKLINE> sage: for t in PartitionTuple([3,2]).components(): ....: print('%s\n' % t.ferrers_diagram()) ... *** ** """
def diagram(self): r""" Return a string for the Ferrers diagram of ``self``.
EXAMPLES::
sage: print(PartitionTuple([[2,1],[3,2],[1,1,1]]).diagram()) ** *** * * ** * * sage: print(PartitionTuple([[3,2],[2,1],[],[1,1,1,1]]).diagram()) *** ** - * ** * * * * sage: PartitionTuples.options(convention="french") sage: print(PartitionTuple([[3,2],[2,1],[],[1,1,1,1]]).diagram()) * * ** * * *** ** - * sage: PartitionTuples.options._reset() """ # There should be a fancier list compression for this but I couldn't get # one to work in the cases where a component was the empty partition else: else:
ferrers_diagram = diagram
def pp(self): r""" Pretty prints this partition tuple. See :meth:`diagram`.
EXAMPLES::
sage: PartitionTuple([[5,5,2,1],[3,2]]).pp() ***** *** ***** ** ** * """
def size(self): """ Return the size of a partition tuple.
EXAMPLES::
sage: PartitionTuple([[2,1],[],[2,2]]).size() 7 sage: PartitionTuple([[],[],[1],[3,2,1]]).size() 7 """
def standard_tableaux(self): """ Return the :class:`standard tableau tuples<StandardTableauTuples>` of this shape.
EXAMPLES::
sage: PartitionTuple([[],[3,2,2,1],[2,2,1],[3]]).standard_tableaux() Standard tableau tuples of shape ([], [3, 2, 2, 1], [2, 2, 1], [3]) """
def up(self): r""" Generator (iterator) for the partition tuples that are obtained from ``self`` by adding a cell.
EXAMPLES::
sage: [mu for mu in PartitionTuple([[],[3,1],[1,1]]).up()] [([1], [3, 1], [1, 1]), ([], [4, 1], [1, 1]), ([], [3, 2], [1, 1]), ([], [3, 1, 1], [1, 1]), ([], [3, 1], [2, 1]), ([], [3, 1], [1, 1, 1])] sage: [mu for mu in PartitionTuple([[],[],[],[]]).up()] [([1], [], [], []), ([], [1], [], []), ([], [], [1], []), ([], [], [], [1])] """
def up_list(self): """ Return a list of the partition tuples that can be formed from ``self`` by adding a cell.
EXAMPLES::
sage: PartitionTuple([[],[3,1],[1,1]]).up_list() [([1], [3, 1], [1, 1]), ([], [4, 1], [1, 1]), ([], [3, 2], [1, 1]), ([], [3, 1, 1], [1, 1]), ([], [3, 1], [2, 1]), ([], [3, 1], [1, 1, 1])] sage: PartitionTuple([[],[],[],[]]).up_list() [([1], [], [], []), ([], [1], [], []), ([], [], [1], []), ([], [], [], [1])]
"""
def down(self): r""" Generator (iterator) for the partition tuples that are obtained from ``self`` by removing a cell.
EXAMPLES::
sage: [mu for mu in PartitionTuple([[],[3,1],[1,1]]).down()] [([], [2, 1], [1, 1]), ([], [3], [1, 1]), ([], [3, 1], [1])] sage: [mu for mu in PartitionTuple([[],[],[]]).down()] []
"""
def down_list(self): """ Return a list of the partition tuples that can be formed from ``self`` by removing a cell.
EXAMPLES::
sage: PartitionTuple([[],[3,1],[1,1]]).down_list() [([], [2, 1], [1, 1]), ([], [3], [1, 1]), ([], [3, 1], [1])] sage: PartitionTuple([[],[],[]]).down_list() [] """
def cells(self): """ Return the coordinates of the cells of ``self``. Coordinates are given as (component index, row index, column index) and are 0 based.
EXAMPLES::
sage: PartitionTuple([[2,1],[1],[1,1,1]]).cells() [(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (2, 0, 0), (2, 1, 0), (2, 2, 0)] """
def content(self, k,r,c, multicharge): r""" Returns the content of the cell.
Let `m_k =` ``multicharge[k]``, then the content of a cell is `m_k + c - r`.
If the ``multicharge`` is a list of integers then it simply offsets the values of the contents in each component. On the other hand, if the ``multicharge`` belongs to `\ZZ/e\ZZ` then the corresponding `e`-residue is returned (that is, the content mod `e`).
As with the content method for partitions, the content of a cell does not technically depend on the partition tuple, but this method is included because it is often useful.
EXAMPLES::
sage: PartitionTuple([[2,1],[2],[1,1,1]]).content(0,1,0, [0,0,0]) -1 sage: PartitionTuple([[2,1],[2],[1,1,1]]).content(0,1,0, [1,0,0]) 0 sage: PartitionTuple([[2,1],[2],[1,1,1]]).content(2,1,0, [0,0,0]) -1
and now we return the 3-residue of a cell::
sage: multicharge = [IntegerModRing(3)(c) for c in [0,0,0]] sage: PartitionTuple([[2,1],[2],[1,1,1]]).content(0,1,0, multicharge) 2
"""
def conjugate(self): """ Return the conjugate partition tuple of ``self``.
The conjugate partition tuple is obtained by reversing the order of the components and then swapping the rows and columns in each component.
EXAMPLES::
sage: PartitionTuple([[2,1],[1],[1,1,1]]).conjugate() ([3], [1], [2, 1])
"""
def dominates(self, mu): r""" Return ``True`` if the PartitionTuple dominates or equals `\mu` and ``False`` otherwise.
Given partition tuples `\mu=(\mu^{(1)},...,\mu^{(m)})` and `\nu=(\nu^{(1)},...,\nu^{(n)})` then `\mu` dominates `\nu` if
.. MATH::
\sum_{k=1}^{l-1} |\mu^{(k)}| +\sum_{r \geq 1} \mu^{(l)}_r \geq \sum_{k=1}^{l-1} |\nu^{(k)}| + \sum_{r \geq 1} \nu^{(l)}_r
EXAMPLES::
sage: mu=PartitionTuple([[1,1],[2],[2,1]]) sage: nu=PartitionTuple([[1,1],[1,1],[2,1]]) sage: mu.dominates(mu) True sage: mu.dominates(nu) True sage: nu.dominates(mu) False sage: tau=PartitionTuple([[],[2,1],[]]) sage: tau.dominates([[2,1],[],[]]) False sage: tau.dominates([[],[],[2,1]]) True """ except ValueError: raise ValueError('%s must be a PartitionTuple' % mu)
@cached_method def initial_tableau(self): r""" Return the :class:`StandardTableauTuple` which has the numbers `1, 2, \ldots, n`, where `n` is the :meth:`size` of ``self``, entered in order from left to right along the rows of each component, where the components are ordered from left to right.
EXAMPLES::
sage: PartitionTuple([ [2,1],[3,2] ]).initial_tableau() ([[1, 2], [3]], [[4, 5, 6], [7, 8]]) """
@cached_method def initial_column_tableau(self): r""" Return the initial column tableau of shape ``self``.
The initial column tableau of shape `\lambda` is the standard tableau that has the numbers `1` to `n`, where `n` is the :meth:`size` of `\lambda`, entered in order from top to bottom, and then left to right, down the columns of each component, starting from the rightmost component and working to the left.
EXAMPLES::
sage: PartitionTuple([ [3,1],[3,2] ]).initial_column_tableau() ([[6, 8, 9], [7]], [[1, 3, 5], [2, 4]]) """
def garnir_tableau(self, *cell): r""" Return the Garnir tableau of shape ``self`` corresponding to the cell ``cell``.
If ``cell`` `= (k,a,c)` then `(k,a+1,c)` must belong to the diagram of the :class:`PartitionTuple`. If this is not the case then we return ``False``.
.. NOTE::
The function also sets ``g._garnir_cell`` equal to ``cell`` which is used by some other functions.
The Garnir tableaux play an important role in integral and non-semisimple representation theory because they determine the "straightening" rules for the Specht modules over an arbitrary ring.
The Garnir tableau are the "first" non-standard tableaux which arise when you act by simple transpositions. If `(k,a,c)` is a cell in the Young diagram of a partition, which is not at the bottom of its column, then the corresponding Garnir tableau has the integers `1, 2, \ldots, n` entered in order from left to right along the rows of the diagram up to the cell `(k,a,c-1)`, then along the cells `(k,a+1,1)` to `(k,a+1,c)`, then `(k,a,c)` until the end of row `a` and then continuing from left to right in the remaining positions. The examples below probably make this clearer!
EXAMPLES::
sage: PartitionTuple([[5,3],[2,2],[4,3]]).garnir_tableau((0,0,2)).pp() 1 2 6 7 8 9 10 13 14 15 16 3 4 5 11 12 17 18 19 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((0,0,2)).pp() 1 2 6 7 8 12 13 16 17 18 19 3 4 5 14 15 20 21 22 9 10 11 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((0,1,2)).pp() 1 2 3 4 5 12 13 16 17 18 19 6 7 11 14 15 20 21 22 8 9 10 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((1,0,0)).pp() 1 2 3 4 5 13 14 16 17 18 19 6 7 8 12 15 20 21 22 9 10 11 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((1,0,1)).pp() 1 2 3 4 5 12 15 16 17 18 19 6 7 8 13 14 20 21 22 9 10 11 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((2,0,1)).pp() 1 2 3 4 5 12 13 16 19 20 21 6 7 8 14 15 17 18 22 9 10 11 sage: PartitionTuple([[5,3,3],[2,2],[4,3]]).garnir_tableau((2,1,1)).pp() Traceback (most recent call last): ... ValueError: (comp, row+1, col) must be inside the diagram
.. SEEALSO::
- :meth:`top_garnir_tableau` """
def top_garnir_tableau(self,e,cell): r""" Return the most dominant *standard* tableau which dominates the corresponding Garnir tableau and has the same residue that has shape ``self`` and is determined by ``e`` and ``cell``.
The Garnir tableau play an important role in integral and non-semisimple representation theory because they determine the "straightening" rules for the Specht modules over an arbitrary ring. The *top Garnir tableaux* arise in the graded representation theory of the symmetric groups and higher level Hecke algebras. They were introduced in [KMR]_.
If the Garnir node is ``cell=(k,r,c)`` and `m` and `M` are the entries in the cells ``(k,r,c)`` and ``(k,r+1,c)``, respectively, in the initial tableau then the top ``e``-Garnir tableau is obtained by inserting the numbers `m, m+1, \ldots, M` in order from left to right first in the cells in row ``r+1`` which are not in the ``e``-Garnir belt, then in the cell in rows ``r`` and ``r+1`` which are in the Garnir belt and then, finally, in the remaining cells in row ``r`` which are not in the Garnir belt. All other entries in the tableau remain unchanged.
If ``e = 0``, or if there are no ``e``-bricks in either row ``r`` or ``r+1``, then the top Garnir tableau is the corresponding Garnir tableau.
EXAMPLES::
sage: PartitionTuple([[3,3,2],[5,4,3,2]]).top_garnir_tableau(2,(1,0,2)).pp() 1 2 3 9 10 12 13 16 4 5 6 11 14 15 17 7 8 18 19 20 21 22 sage: PartitionTuple([[3,3,2],[5,4,3,2]]).top_garnir_tableau(2,(1,0,1)).pp() 1 2 3 9 10 11 12 13 4 5 6 14 15 16 17 7 8 18 19 20 21 22 sage: PartitionTuple([[3,3,2],[5,4,3,2]]).top_garnir_tableau(3,(1,0,1)).pp() 1 2 3 9 12 13 14 15 4 5 6 10 11 16 17 7 8 18 19 20 21 22
sage: PartitionTuple([[3,3,2],[5,4,3,2]]).top_garnir_tableau(3,(3,0,1)).pp() Traceback (most recent call last): ... ValueError: (comp, row+1, col) must be inside the diagram
.. SEEALSO::
- :meth:`~sage.combinat.partition.Partition_tuple.garnir_tableau`
REFERENCE:
.. [KMR] \A. Kleshchev, A. Mathas, and A. Ram, *Universal Specht modules for cyclotomic Hecke algebras*, Proc. London Math. Soc. (2012) 105 (6): 1245-1289. :arxiv:`1102.3519v1`
"""
# now we will put the number m,m+1,...,t[row+1][col] in order into t
def arm_length(self, k,r,c): """ Return the length of the arm of cell ``(k, r, c)`` in ``self``.
INPUT:
- ``k`` -- The component - ``r`` -- The row - ``c`` -- The cell
OUTPUT:
- The arm length as an integer
The arm of cell ``(k, r, c)`` is the number of cells in the ``k``-th component which are to the right of the cell in row ``r`` and column ``c``.
EXAMPLES::
sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).arm_length(2,0,0) 1 sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).arm_length(2,0,1) 0 sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).arm_length(2,2,0) 0 """ except IndexError: raise ValueError("The cell %s is not in the diagram" %((k,r,c),))
def leg_length(self, k,r,c): """ Return the length of the leg of cell ``(k, r, c)`` in ``self``.
INPUT:
- ``k`` -- The component - ``r`` -- The row - ``c`` -- The cell
OUTPUT:
- The leg length as an integer
The leg of cell ``(k, r, c)`` is the number of cells in the ``k``-th component which are below the node in row ``r`` and column ``c``.
EXAMPLES::
sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).leg_length(2,0,0) 2 sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).leg_length(2,0,1) 1 sage: PartitionTuple([[],[2,1],[2,2,1],[3]]).leg_length(2,2,0) 0 """ except IndexError: raise ValueError("The cell is not in the diagram")
def contains(self, mu): r""" Returns ``True`` if this partition tuple contains `\mu`.
If `\lambda=(\lambda^{(1)}, \ldots, \lambda^{(l)})` and `\mu=(\mu^{(1)}, \ldots, \mu^{(m)})` are two partition tuples then `\lambda` contains `\mu` if `m \leq l` and `\mu^{(i)}_r \leq \lambda^{(i)}_r` for `1 \leq i \leq m` and `r \geq 0`.
EXAMPLES::
sage: PartitionTuple([[1,1],[2],[2,1]]).contains( PartitionTuple([[1,1],[2],[2,1]]) ) True """
def hook_length(self, k,r,c): r""" Return the length of the hook of cell ``(k, r, c)`` in the partition.
The hook of cell ``(k, r, c)`` is defined as the cells to the right or below (in the English convention). If your coordinates are in the form ``(k,r,c)``, use Python's \*-operator.
EXAMPLES::
sage: mu=PartitionTuple([[1,1],[2],[2,1]]) sage: [ mu.hook_length(*c) for c in mu.cells()] [2, 1, 2, 1, 3, 1, 1] """ except IndexError: raise ValueError("The cell is not in the diagram")
def to_exp(self, k=0): """ Return a tuple of the multiplicities of the parts of a partition.
Use the optional parameter ``k`` to get a return list of length at least ``k``.
EXAMPLES::
sage: PartitionTuple([[1,1],[2],[2,1]]).to_exp() ([2], [0, 1], [1, 1]) sage: PartitionTuple([[1,1],[2,2,2,2],[2,1]]).to_exp() ([2], [0, 4], [1, 1])
"""
def removable_cells(self): """ Returns a list of the removable cells of this partition tuple.
All indices are of the form ``(k, r, c)``, where ``r`` is the row-index, ``c`` is the column index and ``k`` is the component.
EXAMPLES::
sage: PartitionTuple([[1,1],[2],[2,1]]).removable_cells() [(0, 1, 0), (1, 0, 1), (2, 0, 1), (2, 1, 0)] sage: PartitionTuple([[1,1],[4,3],[2,1,1]]).removable_cells() [(0, 1, 0), (1, 0, 3), (1, 1, 2), (2, 0, 1), (2, 2, 0)]
"""
corners = removable_cells # for compatibility with partitions
def addable_cells(self): """ Return a list of the removable cells of this partition tuple.
All indices are of the form ``(k, r, c)``, where ``r`` is the row-index, ``c`` is the column index and ``k`` is the component.
EXAMPLES::
sage: PartitionTuple([[1,1],[2],[2,1]]).addable_cells() [(0, 0, 1), (0, 2, 0), (1, 0, 2), (1, 1, 0), (2, 0, 2), (2, 1, 1), (2, 2, 0)] sage: PartitionTuple([[1,1],[4,3],[2,1,1]]).addable_cells() [(0, 0, 1), (0, 2, 0), (1, 0, 4), (1, 1, 3), (1, 2, 0), (2, 0, 2), (2, 1, 1), (2, 3, 0)]
"""
outside_corners = addable_cells # for compatibility with partitions
def add_cell(self, k,r,c): r""" Return the partition tuple obtained by adding a cell in row ``r``, column ``c``, and component ``k``.
This does not change ``self``.
EXAMPLES::
sage: PartitionTuple([[1,1],[4,3],[2,1,1]]).add_cell(0,0,1) ([2, 1], [4, 3], [2, 1, 1])
""" else: raise ValueError("%s is not an addable cell"%((k,r,c),))
def remove_cell(self, k,r,c): """ Return the partition tuple obtained by removing a cell in row ``r``, column ``c``, and component ``k``.
This does not change ``self``.
EXAMPLES::
sage: PartitionTuple([[1,1],[4,3],[2,1,1]]).remove_cell(0,1,0) ([1], [4, 3], [2, 1, 1])
""" else: raise ValueError("%s is not a removable cell"%((k,r,c),))
def to_list(self): r""" Return ``self`` as a list of lists.
EXAMPLES::
sage: PartitionTuple([[1,1],[4,3],[2,1,1]]).to_list() [[1, 1], [4, 3], [2, 1, 1]]
TESTS::
sage: all(mu==PartitionTuple(mu.to_list()) for mu in PartitionTuples(4,4)) True """
def young_subgroup(self): """ Return the corresponding Young, or parabolic, subgroup of the symmetric group.
EXAMPLES::
sage: PartitionTuple([[2,1],[4,2],[1]]).young_subgroup() Permutation Group with generators [(), (8,9), (6,7), (5,6), (4,5), (1,2)] """
def young_subgroup_generators(self): """ Return an indexing set for the generators of the corresponding Young subgroup.
EXAMPLES::
sage: PartitionTuple([[2,1],[4,2],[1]]).young_subgroup_generators() [1, 4, 5, 6, 8] """
@cached_method def _initial_degree(self,e,multicharge): r""" Return the Brundan-Kleshchev-Wang degree of the initial tableau of shape ``self``.
This degree depends only the shape of the tableau and it is used as the base case for computing the degrees of all tableau of shape ``self``, which is why this method is cached. See :meth:`sage.combinat.tableau.Tableau.degree` for more information.
EXAMPLES::
sage: PartitionTuple([[2,1],[2,2]])._initial_degree(0,(0,0)) 1 sage: PartitionTuple([[2,1],[2,2]])._initial_degree(2,(0,0)) 4 sage: PartitionTuple([[2,1],[2,2]])._initial_degree(3,(0,0)) 1 sage: PartitionTuple([[2,1],[2,2]])._initial_degree(4,(0,0)) 1 """ else:
def degree(self, e): r""" Return the ``e``-th degree of ``self``.
The `e`-th degree is the sum of the degrees of the standard tableaux of shape `\lambda`. The `e`-th degree is the exponent of `\Phi_e(q)` in the Gram determinant of the Specht module for a semisimple cyclotomic Hecke algebra of type `A` with parameter `q`.
For this calculation the multicharge `(\kappa_1, \ldots, \kappa_l)` is chosen so that `\kappa_{r+1} - \kappa_r > n`, where `n` is the :meth:`size` of `\lambda` as this ensures that the Hecke algebra is semisimple.
INPUT:
- ``e`` -- an integer `e > 1`
OUTPUT:
A non-negative integer.
EXAMPLES::
sage: PartitionTuple([[2,1],[2,2]]).degree(2) 532 sage: PartitionTuple([[2,1],[2,2]]).degree(3) 259 sage: PartitionTuple([[2,1],[2,2]]).degree(4) 196 sage: PartitionTuple([[2,1],[2,2]]).degree(5) 105 sage: PartitionTuple([[2,1],[2,2]]).degree(6) 105 sage: PartitionTuple([[2,1],[2,2]]).degree(7) 0
Therefore, the Gram determinant of `S(2,1|2,2)` when the Hecke parameter `q` is "generic" is
.. MATH::
q^N \Phi_2(q)^{532}\Phi_3(q)^{259}\Phi_4(q)^{196}\Phi_5(q)^{105}\Phi_6(q)^{105}
for some integer `N`. Compare with :meth:`prime_degree`. """
def prime_degree(self, p): r""" Return the ``p``-th prime degree of ``self``.
The degree of a partition `\lambda` is the sum of the `e`-degrees` of the standard tableaux of shape `\lambda` (see :meth:`degree`), for `e` a power of the prime `p`. The prime degree gives the exponent of `p` in the Gram determinant of the integral Specht module of the symmetric group.
The `p`-th degree is the sum of the degrees of the standard tableaux of shape `\lambda`. The `p`-th degree is the exponent of `p` in the Gram determinant of a semisimple cyclotomic Hecke algebra of type `A` with parameter `q = 1`.
As with :meth:`degree`, for this calculation the multicharge `(\kappa_1, \ldots, \kappa_l)` is chosen so that `\kappa_{r+1} - \kappa_r > n`, where `n` is the :meth:`size` of `\lambda` as this ensures that the Hecke algebra is semisimple.
INPUT:
- ``e`` -- an integer `e > 1` - ``muticharge`` -- an `l`-tuple of integers, where `l` is the :meth:`level` of ``self``
OUTPUT:
A non-negative integer
EXAMPLES::
sage: PartitionTuple([[2,1],[2,2]]).prime_degree(2) 728 sage: PartitionTuple([[2,1],[2,2]]).prime_degree(3) 259 sage: PartitionTuple([[2,1],[2,2]]).prime_degree(5) 105 sage: PartitionTuple([[2,1],[2,2]]).prime_degree(7) 0
Therefore, the Gram determinant of `S(2,1|2,2)` when `q=1` is `2^{728} 3^{259}5^{105}`. Compare with :meth:`degree`. """
def defect(self, e, multicharge): r""" Return the ``e``-defect or the ``e``-weight ``self``.
The `e`-defect is the number of (connected) `e`-rim hooks that can be removed from the partition.
The defect of a partition tuple is given by
.. MATH::
\text{defect}(\beta) = (\Lambda, \beta) - \tfrac12(\beta, \beta)
where `\Lambda = \sum_r \Lambda_{\kappa_r}` for the multicharge `(\kappa_1, \ldots, \kappa_{\ell})` and `\beta = \sum_{(r,c)} \alpha_{(c-r) \pmod e}`, with the sum being over the cells in the partition.
EXAMPLES::
sage: PartitionTuple([[2,2],[2,2]]).defect(0,(0,0)) 0 sage: PartitionTuple([[2,2],[2,2]]).defect(2,(0,0)) 8 sage: PartitionTuple([[2,2],[2,2]]).defect(2,(0,1)) 8 sage: PartitionTuple([[2,2],[2,2]]).defect(3,(0,2)) 7 sage: PartitionTuple([[2,2],[2,2]]).defect(3,(0,2)) 7 sage: PartitionTuple([[2,2],[2,2]]).defect(3,(3,2)) 7 sage: PartitionTuple([[2,2],[2,2]]).defect(4,(0,0)) 0 """ # Will correspond to an element of the positive root lattice # corresponding to the block. # We use a dictionary to cover the case when e = 0.
for r in beta)
#-------------------------------------------------- # Partition tuples - parent classes #-------------------------------------------------- class PartitionTuples(UniqueRepresentation, Parent): """ Class of all partition tuples.
For more information about partition tuples, see :class:`PartitionTuple`.
This is a factory class which returns the appropriate parent based on the values of ``level``, ``size``, and ``regular``
INPUT:
- ``level`` -- the length of the tuple
- ``size`` -- the total number of cells
- ``regular`` -- the highest multiplicity an entry may have in a component plus `1`
TESTS::
sage: [ [2,1],[],[3] ] in PartitionTuples() True sage: ( [2,1],[],[3] ) in PartitionTuples() True sage: ( [] ) in PartitionTuples() True
Check that :trac:`14145` has been fixed::
sage: 1 in PartitionTuples() False """
@staticmethod def __classcall_private__(klass, level=None, size=None, regular=None): r""" Return the correct parent object based upon the input.
TESTS::
sage: PartitionTuples() Partition tuples sage: PartitionTuples(3) Partition tuples of level 3 sage: PartitionTuples(size=3) Partition tuples of size 3 sage: PartitionTuples(3,8) Partition tuples of level 3 and size 8 """
# sanity testing raise ValueError('the level must be a positive integer')
raise ValueError('the size must be a non-negative integer')
if size is None: if regular is None: return _Partitions return RegularPartitions_all(regular)
if regular is None: return Partitions_n(size) return RegularPartitions_n(size, regular)
# Higher level
Element = PartitionTuple options=Partitions.options
# default for level _level=None _size=None
def _element_constructor_(self, mu): r""" Constructs an element of :class:`PartitionTuple`.
INPUT:
- ``mu`` -- a tuple of partitions
OUTPUT:
- The corresponding :class:`PartitionTuple` object
TESTS::
sage: PartitionTuple([[2],[2],[]]).parent() Partition tuples sage: parts = PartitionTuples(3) sage: parts([[2,1],[1],[2,2,2]]).parent() is parts True sage: PartitionTuples._element_constructor_(PartitionTuples(), [[2,1],[3,2],[1,1,1]]) ([2, 1], [3, 2], [1, 1, 1]) sage: parts([[1,2]]) Traceback (most recent call last): ... ValueError: [[1, 2]] is not a Partition tuples of level 3 """ # one way or another these two cases need to be treated separately raise ValueError('{} is not a {}'.format(mu, self))
# As partitions are 1-tuples of partitions we need to treat them separately
raise ValueError('{} is not a {}'.format(mu, self))
def __contains__(self, mu): r""" Return ``True`` if `\mu` is in ``self``.
TESTS::
sage: PartitionTuple([[3,2],[2]]) in PartitionTuples() True sage: PartitionTuple([[3,2],[],[],[],[2]]) in PartitionTuples() True sage: PartitionTuple([[2,1],[],[1,1],[],[2]]) in PartitionTuples() True sage: PartitionTuple([[2,1],[],[1,1],[],[3]]) in PartitionTuples() True sage: all(mu in PartitionTuples() for mu in PartitionTuples(3,8)) True sage: [5,1,1] in PartitionTuples() True sage: [[5,1,1]] in PartitionTuples() True sage: la = Partition([3,3,1]) sage: PT = PartitionTuples() sage: la in PT True sage: PT(la) ([3, 3, 1])
Check that :trac:`14145` is fixed::
sage: 1 in PartitionTuples() False """
def __getitem__(self, r): r""" The default implementation of ``__getitem__()`` for enumerated sets does not allow slices, so we override it.
EXAMPLES::
sage: PartitionTuples()[10:20] [([1, 1, 1]), ([2], []), ([1, 1], []), ([1], [1]), ([], [2]), ([], [1, 1]), ([1], [], []), ([], [1], []), ([], [], [1]), ([], [], [], [])] """ raise ValueError('infinite set') else: raise ValueError('r must be an integer or a slice')
# this is to cope with empty slice endpoints like [6:] or [:] raise IndexError('value out of range')
def level(self): """ Return the level or ``None`` if it is not defined.
EXAMPLES::
sage: PartitionTuples().level() is None True sage: PartitionTuples(7).level() 7 """
def size(self): """ Return the size or ``None`` if it is not defined.
EXAMPLES::
sage: PartitionTuples().size() is None True sage: PartitionTuples(size=7).size() 7 """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples().an_element() ([1, 1, 1, 1], [2, 1, 1], [3, 1], [4]) """ return PartitionTuple( ([1,1,1,1],[2,1,1],[3,1],[4]) )
class PartitionTuples_all(PartitionTuples): """ Class of partition tuples of a arbitrary level and arbitrary sum. """
def __init__(self): r""" Initializes the class.
EXAMPLES::
sage: TestSuite( PartitionTuples() ).run() """
def _repr_(self): r""" Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples() Partition tuples """
def __iter__(self): r""" Iterate through the infinite class of partition tuples of arbitrary level and size.
EXAMPLES::
sage: PartitionTuples()[:20] [([]), ([1]), ([], []), ([2]), ([1, 1]), ([1], []), ([], [1]), ([], [], []), ([3]), ([2, 1]), ([1, 1, 1]), ([2], []), ([1, 1], []), ([1], [1]), ([], [2]), ([], [1, 1]), ([1], [], []), ([], [1], []), ([], [], [1]), ([], [], [], [])] """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples().an_element() ([1, 1, 1, 1], [2, 1, 1], [3, 1], [4]) """
class PartitionTuples_level(PartitionTuples): """ Class of partition tuples of a fixed level, but summing to an arbitrary integer. """
def __init__(self, level): r""" Initializes this class.
EXAMPLES::
sage: PartitionTuples(4) Partition tuples of level 4 sage: PartitionTuples(level=6) Partition tuples of level 6 sage: TestSuite( PartitionTuples(level=4) ).run() """ raise ValueError('level must be a non-negative integer')
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(2) Partition tuples of level 2 """
def __contains__(self, mu): r""" Return ``True`` if `\mu` is in ``self``.
TESTS::
sage: PartitionTuple([[3,2],[2]]) in PartitionTuples(2) True sage: PartitionTuple([[3,2],[2]]) in PartitionTuples(level=2) True sage: PartitionTuple([[2,2,1],[2]]) in PartitionTuples(level=2) True sage: PartitionTuple([[2,2,1],[],[2]]) in PartitionTuples(level=2) False sage: all(mu in PartitionTuples(3) for mu in PartitionTuples(3,8)) True
Check that :trac:`14145` is fixed::
sage: 1 in PartitionTuples(level=2) False """ # Note that self._level > 1
def __iter__(self): r""" Iterate through the infinite class of partition tuples of fixed level.
EXAMPLES::
sage: parts=PartitionTuples(3) sage: [parts[k] for k in range(20)] [([], [], []), ([1], [], []), ([], [1], []), ([], [], [1]), ([2], [], []), ([1, 1], [], []), ([1], [1], []), ([1], [], [1]), ([], [2], []), ([], [1, 1], []), ([], [1], [1]), ([], [], [2]), ([], [], [1, 1]), ([3], [], []), ([2, 1], [], []), ([1, 1, 1], [], []), ([2], [1], []), ([1, 1], [1], []), ([2], [], [1]), ([1, 1], [], [1])] """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples(level=4).an_element() ([], [1], [2], [3]) """
class PartitionTuples_size(PartitionTuples): """ Class of partition tuples of a fixed size, but arbitrary level. """ def __init__(self, size): r""" Initializes this class.
EXAMPLES::
sage: PartitionTuples(size=4) Partition tuples of size 4 sage: PartitionTuples(size=6) Partition tuples of size 6
sage: TestSuite( PartitionTuples(size=6) ).run() """ raise ValueError('size must be a non-negative integer')
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(size=4) # indirect doctest Partition tuples of size 4 """
def __contains__(self, mu): r""" Return ``True`` if `\mu` is in ``self``.
TESTS::
sage: PartitionTuple([[3,2],[2]]) in PartitionTuples(size=7) True sage: PartitionTuple([[3,2],[],[],[],[2]]) in PartitionTuples(size=7) True sage: PartitionTuple([[2,1],[],[1,1],[],[2]]) in PartitionTuples(size=7) True sage: PartitionTuple([[2,1],[],[1,1],[],[3]]) in PartitionTuples(size=7) False sage: all(mu in PartitionTuples(size=8) for mu in PartitionTuples(3,8)) True sage: [3, 2, 1] in PartitionTuples(size=7) False
Check that :trac:`14145` is fixed::
sage: 1 in PartitionTuples(size=7) False """
def __iter__(self): r""" Iterates through the infinite class of partition tuples of a fixed size.
EXAMPLES::
sage: PartitionTuples(size=3)[:20] [([3]), ([2, 1]), ([1, 1, 1]), ([3], []), ([2, 1], []), ([1, 1, 1], []), ([2], [1]), ([1, 1], [1]), ([1], [2]), ([1], [1, 1]), ([], [3]), ([], [2, 1]), ([], [1, 1, 1]), ([3], [], []), ([2, 1], [], []), ([1, 1, 1], [], []), ([2], [1], []), ([1, 1], [1], []), ([2], [], [1]), ([1, 1], [], [1])] """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples(size=4).an_element() ([1], [1], [1], [1]) """
class PartitionTuples_level_size(PartitionTuples): """ Class of partition tuples with a fixed level and a fixed size. """
def __init__(self, level, size): r""" Initializes this class.
EXAMPLES::
sage: TestSuite( PartitionTuples(4,2) ).run() sage: TestSuite( PartitionTuples(level=4, size=5) ).run() """ raise ValueError('n and level must be non-negative integers')
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(4,2) Partition tuples of level 4 and size 2 sage: PartitionTuples(size=2,level=4) Partition tuples of level 4 and size 2 """
def __contains__(self, mu): r""" Return ``True`` if ``mu`` is in ``self``.
TESTS::
sage: PartitionTuple([[3,2],[2]]) in PartitionTuples(2,7) True sage: PartitionTuple([[3,2],[],[],[],[2]]) in PartitionTuples(5,7) True sage: PartitionTuple([[2,1],[],[1,1],[],[2]]) in PartitionTuples(5,7) True sage: PartitionTuple([[2,1],[],[1,1],[],[3]]) in PartitionTuples(2,8) False sage: all(mu in PartitionTuples(3,8) for mu in PartitionTuples(3,8)) True
Check that :trac:`14145` is fixed::
sage: 1 in PartitionTuples(5,7) False """ return self._size == sum(mu) and self._level == len(mu) and self._size == sum(map(sum,mu)))
def __iter__(self): r""" Iterates through the finite class of partition tuples of a fixed level and a fixed size.
EXAMPLES::
sage: PartitionTuples(2,0).list() #indirect doctest [([], [])] sage: PartitionTuples(2,1).list() #indirect doctest [([1], []), ([], [1])] sage: PartitionTuples(2,2).list() #indirect doctest [([2], []), ([1, 1], []), ([1], [1]), ([], [2]), ([], [1, 1])] sage: PartitionTuples(3,2).list() #indirect doctest [([2], [], []), ([1, 1], [], []), ([1], [1], []), ([1], [], [1]), ([], [2], []), ([], [1, 1], []), ([], [1], [1]), ([], [], [2]), ([], [], [1, 1])] """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples(level=4,size=4).an_element() ([1], [], [], [3]) """ else:
def cardinality(self): r""" Returns the number of ``level``-tuples of partitions of size ``n``.
Wraps a pari function call.
EXAMPLES::
sage: PartitionTuples(2,3).cardinality() 10 sage: PartitionTuples(2,8).cardinality() 185
TESTS:
The following calls used to fail (:trac:`11476`)::
sage: PartitionTuples(17,2).cardinality() 170 sage: PartitionTuples(2,17).cardinality() 8470 sage: PartitionTuples(100,13).cardinality() 110320020147886800 sage: PartitionTuples(13,90).cardinality() 91506473741200186152352843611
These answers were checked against Gap4 (the last of which takes an awful long time for gap to compute). """
def __setstate__(self, state): r""" In order to maintain backwards compatibility and be able to unpickle a old pickle from PartitionTuples_nk we have to override the default ``__setstate__``.
TESTS::
sage: loads(b"x\x9cM\x90\xcdN\xc30\x0c\x80\xd5\xc1\x06\xeb\x80\xf1{\xe0\r\xe0\xd2\x0b\x07\x1e\x02)B\x88\x9c-7\xb5\xba\xa8MR')\x12\x07$8p\xe0\xadq\x996q\xb1b\xfb\xb3\xf59\x9f3\x93\xb0\xa5\xca\x04W[\x8f\xb9\x1a0f\x9bm\xf0\xe5\xf3\xee\xf5:\x0e=%\xf0]\xc9\xc5\xfd\x17\xcf>\xf8\xe0N_\x83\xf5\xd2\xc5\x1e\xd0L\x10\xf46e>T\xba\x04r55\x8d\xf5-\xcf\x95p&\xf87\x8a\x19\x1c\xe5Mh\xc0\xa3#^(\xbd\x00\xd3`F>Rz\t\x063\xb5!\xbe\xf3\xf1\xd4\x98\x90\xc4K\xa5\x0b\xbf\xb5\x8b\xb2,U\xd6\x0bD\xb1t\xd8\x11\xec\x12.u\xf1\xf0\xfd\xc2+\xbd\x82\x96<E\xcc!&>Qz\x0e5&\xe2S\xa5\xd70X\xd3\xf5\x04\xe2\x91\xc4\x95\xcf\x9e\n\x11\xa3\x9e\x1c\xf9<\t\xa6\x1cG#\x83\xbcV\xfaf\x7f\xd9\xce\xfc\xef\xb4s\xa5o\xf7#\x13\x01\x03\xa6$!J\x81/~t\xd1m\xc4\xe5Q\\.\xff\xfd\x8e\t\x14\rmW\\\xa9\xb1\xae~\x01/\x8f\x85\x02") Partition tuples of level 7 and size 3 sage: loads(dumps( PartitionTuples(7,3) )) # indirect doctest for unpickling a Tableau element Partition tuples of level 7 and size 3 """ else: super(PartitionTuples, self).__setstate__(state)
############################################################################### ## Regular partition tuples
class RegularPartitionTuples(PartitionTuples): """ Abstract base class for `\ell`-regular partition tuples. """ def __init__(self, regular, **kwds): """ Initialize ``self``.
TESTS::
sage: RPT = PartitionTuples(regular=3) sage: TestSuite(RPT).run() """ raise ValueError("regular must be an integer greater than 1")
def __contains__(self, mu): r""" Check if ``mu`` is an `\ell`-regular partition tuple.
TESTS::
sage: RPT = PartitionTuples(regular=2) sage: [[11,1], [2]] in RPT True sage: Partition([4,1]) in RPT True sage: [5,4,3,2,1] in RPT True sage: [[6,3,1], [], [], [3,1], [1], [1], [1]] in RPT True sage: [[10], [1], [1,1], [4,2]] in RPT False sage: [[5,2], [17, 1], [], [3,3,1], [1,1]] in RPT False sage: RPT = PartitionTuples(4,2,3) sage: elt = RPT([[1], [], [], [1]]) sage: elt in RPT True """ return False return True
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples(regular=2).an_element() ([1], [], [], [2]) """ else: else:
class RegularPartitionTuples_all(RegularPartitionTuples): """ Class of `\ell`-regular partition tuples. """ def __init__(self, regular): r""" Initialize ``self``.
EXAMPLES::
sage: RPT = PartitionTuples(regular=3) sage: TestSuite(RPT).run() """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(regular=3) 3-Regular partition tuples """
def __iter__(self): r""" Iterate through the class of `\ell`-regular partition tuples.
EXAMPLES::
sage: PartitionTuples(regular=2)[:20] [([]), ([], []), ([1]), ([], [], []), ([1], []), ([], [1]), ([2]), ([], [], [], []), ([1], [], []), ([], [1], []), ([], [], [1]), ([2], []), ([1], [1]), ([], [2]), ([3]), ([2, 1]), ([], [], [], [], []), ([1], [], [], []), ([], [1], [], []), ([], [], [1], [])] """
class RegularPartitionTuples_level(RegularPartitionTuples): """ Class of `\ell`-regular partition tuples with a fixed level. """ def __init__(self, level, regular): r""" Initialize ``self``.
EXAMPLES::
sage: RPT = PartitionTuples(level=4, regular=3) sage: TestSuite(RPT).run() """ raise ValueError('level must be a positive integer') else: category = FiniteEnumeratedSets()
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(level=4, regular=3) 3-Regular partition tuples of level 4 """
def __contains__(self, mu): r""" Return ``True`` if ``mu`` is in ``self``.
TESTS::
sage: RPT = PartitionTuples(level=4, regular=2) sage: [[4,2,1], [], [2], [2]] in RPT True sage: [[10], [1], [1,1], [4,2]] in RPT False sage: [[5,2], [], [3,3,1], [1,1]] in RPT False sage: [4, 3, 2] in RPT False """ if mu[0] in ZZ: return mu in RegularPartitions_all(self._ell)
def __iter__(self): r""" Iterate through the class of `\ell`-regular partition tuples of a fixed level.
EXAMPLES::
sage: PartitionTuples(level=4, regular=2)[:20] [([], [], [], []), ([1], [], [], []), ([], [1], [], []), ([], [], [1], []), ([], [], [], [1]), ([2], [], [], []), ([1], [1], [], []), ([1], [], [1], []), ([1], [], [], [1]), ([], [2], [], []), ([], [1], [1], []), ([], [1], [], [1]), ([], [], [2], []), ([], [], [1], [1]), ([], [], [], [2]), ([3], [], [], []), ([2, 1], [], [], []), ([2], [1], [], []), ([2], [], [1], []), ([2], [], [], [1])] """
class RegularPartitionTuples_size(RegularPartitionTuples): """ Class of `\ell`-regular partition tuples with a fixed size. """ def __init__(self, size, regular): r""" Initialize ``self``.
EXAMPLES::
sage: RPT = PartitionTuples(size=4, regular=3) sage: TestSuite(RPT).run() """ raise ValueError('size must be a non-negative integer')
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(size=4, regular=3) 3-Regular partition tuples of size 4 """
def __contains__(self, mu): r""" Return ``True`` if ``mu`` is in ``self``.
TESTS::
sage: RPT = PartitionTuples(size=4, regular=2) sage: [[2, 1], [1]] in RPT True sage: [3, 1] in RPT True sage: [[1], [], [], [2,1]] in RPT True sage: [[1], [1], [1], [1]] in RPT True sage: [[1], [1,1,1]] in RPT False sage: [[2,1,1]] in RPT False sage: [2,1,1] in RPT False sage: RPT = PartitionTuples(size=7, regular=2) sage: [[], [3,2,2,1], [1], [1]] in RPT False sage: RPT = PartitionTuples(size=9, regular=2) sage: [4, 3, 2] in RPT True """ or (RegularPartitionTuples.__contains__(self, mu) and self._size == sum(map(sum,mu))) )
def __iter__(self): r""" Iterate through the class of `\ell`-regular partition tuples of a fixed size.
EXAMPLES::
sage: PartitionTuples(size=4, regular=2)[:10] [([4]), ([3, 1]), ([4], []), ([3, 1], []), ([3], [1]), ([2, 1], [1]), ([2], [2]), ([1], [3]), ([1], [2, 1]), ([], [4])] """
class RegularPartitionTuples_level_size(RegularPartitionTuples): """ Class of `\ell`-regular partition tuples with a fixed level and a fixed size. """ def __init__(self, level, size, regular): r""" Initialize ``self``.
EXAMPLES::
sage: RPT = PartitionTuples(4,2,3) sage: TestSuite(RPT).run() """ raise ValueError('size must be a non-negative integer') raise ValueError('level must be a positive integer')
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: PartitionTuples(4,2,3) 3-Regular partition tuples of level 4 and size 2 sage: PartitionTuples(size=2,level=4,regular=3) 3-Regular partition tuples of level 4 and size 2 """
def __contains__(self, mu): r""" Return ``True`` if `\mu` is in ``self``.
TESTS::
sage: RPT = PartitionTuples(4,3,2) sage: [[], [], [2], [1]] in RPT True sage: [[1], [1], [], [1]] in RPT True sage: [[1,1,1], [], [], []] in RPT False sage: RPT = PartitionTuples(9, 3, 2) sage: [4, 3, 2] in RPT False """ return mu in RegularPartitions_all(self._ell) and self._size == sum(mu) and self._level == len(mu) and self._size == sum(map(sum,mu)))
def __iter__(self): r""" Iterate through the finite class of `\ell`-regular partition tuples of a fixed level and a fixed size.
EXAMPLES::
sage: list(PartitionTuples(3,3,2)) [([3], [], []), ([2, 1], [], []), ([2], [1], []), ([2], [], [1]), ([1], [2], []), ([1], [1], [1]), ([1], [], [2]), ([], [3], []), ([], [2, 1], []), ([], [2], [1]), ([], [1], [2]), ([], [], [3]), ([], [], [2, 1])] """
def _an_element_(self): """ Return a generic element.
EXAMPLES::
sage: PartitionTuples(level=4, size=4, regular=3).an_element() ([1], [], [], [3]) """ mu = [self._size-1,1] else:
# Deprecations from trac:18555. July 2016 from sage.misc.superseded import deprecated_function_alias PartitionTuples.global_options=deprecated_function_alias(18555, PartitionTuples.options) |