def __classcall_private__(cls, part, k):
        r"""
        Implements the shortcut ``Core(part, k)`` to ``Cores(k,l)(part)``
        where `l` is the length of the core.

        TESTS::

            sage: c = Core([2,1],4); c
            [2, 1]
            sage: c.parent()
            4-Cores of length 3
            sage: type(c)
            <class 'sage.combinat.core.Cores_length_with_category.element_class'>

            sage: Core([2,1],3)
            Traceback (most recent call last):
            ...
            ValueError: [2, 1] is not a 3-core
        """
        if isinstance(part, cls):
            return part
        part = Partition(part)
        if not part.is_core(k):
            raise ValueError, "%s is not a %s-core"%(part, k)
        l = sum(part.k_boundary(k).row_lengths())
        return Cores(k, l)(part)

    def __init__(self, core, parent):
        """
        TESTS::

            sage: C = Cores(4,3)
            sage: c = C([2,1]); c
            [2, 1]
            sage: type(c)
            <class 'sage.combinat.core.Cores_length_with_category.element_class'>
            sage: c.parent()
            4-Cores of length 3
            sage: TestSuite(c).run()

            sage: C = Cores(3,3)
            sage: C([2,1])
            Traceback (most recent call last):
            ...
            ValueError: [2, 1] is not a 3-core
        """
        k = parent.k
        part = Partition(core)
        if not part.is_core(k):
            raise ValueError, "%s is not a %s-core"%(part, k)
        CombinatorialObject.__init__(self, core)
        Element.__init__(self, parent)

        def sum_of_partitions(self, la):
            r"""
            Return the sum over all sets partitions whose shape is ``la``,
            scaled by `\prod_i m_i!` where `m_i` is the multiplicity
            of `i` in ``la``.

            INPUT:

            - ``la`` -- an integer partition

            OUTPUT:

            - an element of ``self``

            EXAMPLES::

                sage: w = SymmetricFunctionsNonCommutingVariables(QQ).dual().w()
                sage: w.sum_of_partitions([2,1,1])
                2*w{{1}, {2}, {3, 4}} + 2*w{{1}, {2, 3}, {4}} + 2*w{{1}, {2, 4}, {3}}
                 + 2*w{{1, 2}, {3}, {4}} + 2*w{{1, 3}, {2}, {4}} + 2*w{{1, 4}, {2}, {3}}
            """
            la = Partition(la)
            c = prod([factorial(_) for _ in la.to_exp()])
            P = SetPartitions()
            return self.sum_of_terms([(P(m), c) for m in SetPartitions(sum(la), la)], distinct=True)

    def __init__(self, partition, ring=None, cache_matrices=True):
        r"""
        An irreducible representation of the symmetric group corresponding
        to ``partition``.

        For more information, see the documentation for
        :func:`SymmetricGroupRepresentation`.

        EXAMPLES::

            sage: spc = SymmetricGroupRepresentation([3])
            sage: spc([3,2,1])
            [1]
            sage: spc == loads(dumps(spc))
            True

            sage: spc = SymmetricGroupRepresentation([3], cache_matrices=False)
            sage: spc([3,2,1])
            [1]
            sage: spc == loads(dumps(spc))
            True
        """
        self._partition = Partition(partition)
        self._ring = ring if not ring is None else self._default_ring
        if cache_matrices is False:
            self.representation_matrix = self._representation_matrix_uncached

        def affine_grassmannian_to_core(self):
            r"""
            Bijection between affine Grassmannian elements of type `A_k^{(1)}` and `(k+1)`-cores.

            INPUT:

            - ``self`` -- an affine Grassmannian element of some affine Weyl group of type `A_k^{(1)}`

            Recall that an element `w` of an affine Weyl group is
            affine Grassmannian if all its all reduced words end in 0, see :meth:`is_affine_grassmannian`.

            OUTPUT:

            - a `(k+1)`-core

            See also :meth:`affine_grassmannian_to_partition`.

            EXAMPLES::

                sage: W = WeylGroup(['A',2,1])
                sage: w = W.from_reduced_word([0,2,1,0])
                sage: la = w.affine_grassmannian_to_core(); la
                [4, 2]
                sage: type(la)
                <class 'sage.combinat.core.Cores_length_with_category.element_class'>
                sage: la.to_grassmannian() == w
                True

                sage: w = W.from_reduced_word([0,2,1])
                sage: w.affine_grassmannian_to_core()
                Traceback (most recent call last):
                ...
                ValueError: Error! this only works on type 'A' affine Grassmannian elements
            """
            from sage.combinat.partition import Partition
            from sage.combinat.core import Core

            if not self.is_affine_grassmannian() or not self.parent().cartan_type().letter == "A":
                raise ValueError("Error! this only works on type 'A' affine Grassmannian elements")
            out = Partition([])
            rword = self.reduced_word()
            kp1 = self.parent().n
            for i in range(len(rword)):
                for c in (x for x in out.outside_corners() if (x[1] - x[0]) % kp1 == rword[-i - 1]):
                    out = out.add_cell(c[0], c[1])
            return Core(out._list, kp1)

    def Podium(data):
        r"""
        If ``data`` is an integer than the standard podium with ``data`` steps is
        returned. Otherwise, ``data`` should be a weakly decreasing list of integers
        (i.e. a integer partition).

        EXAMPLES::

            sage: from surface_dynamics.all import *

            sage: o = origamis.Podium([3,3,2,1])
            sage: o
            Podium origami with partition [3, 3, 2, 1]
            sage: print o
            (1,2,3)(4,5,6)(7,8)(9)
            (1,4,7,9)(2,5,8)(3,6)
        """
        from sage.combinat.partition import Partition

        if isinstance(data, (int,Integer)):
            p = Partition([i for i in xrange(data,0,-1)])
        else:
            p = Partition(data)

        p = Partition(data)
        q = p.conjugate()

        r=[]
        positions = []
        i = 0
        for j,jj in enumerate(p):
            r.extend(xrange(i+1,i+jj))
            r.append(i)
            i += jj
            positions.extend((k,j) for k in xrange(jj))

        u = [None]*sum(p)
        for j in xrange(len(q)):
            k = j
            for jj in xrange(q[j]-1):
                u[k] = k+p[jj]
                k += p[jj]
            u[k] = j

        return Origami(r,u,positions=positions,name="Podium origami with partition %s" %str(p),as_tuple=True)

    def __classcall_private__(cls, shape, weight):
        r"""
        Straighten arguments before unique representation.

        TESTS::

            sage: LR = LittlewoodRichardsonTableaux([3,2,1],[[2,1],[2,1]])
            sage: TestSuite(LR).run()
            sage: LittlewoodRichardsonTableaux([3,2,1],[[2,1]])
            Traceback (most recent call last):
            ...
            ValueError: the sizes of shapes and sequence of weights do not match
        """
        shape = Partition(shape)
        weight = tuple(Partition(a) for a in weight)
        if shape.size() != sum(a.size() for a in weight):
            raise ValueError("the sizes of shapes and sequence of weights do not match")
        return super(LittlewoodRichardsonTableaux, cls).__classcall__(cls, shape, weight)

    def __classcall_private__(cls, deg, par):
        r"""
        Create a primary similarity class type.

        EXAMPLES::

            sage: PrimarySimilarityClassType(2, [3, 2, 1])
            [2, [3, 2, 1]]

        The parent class is the class of primary similarity class types of order
        `d|\lambda\`::

            sage: PT = PrimarySimilarityClassType(2, [3, 2, 1])
            sage: PT.parent().size()
            12
        """
        par = Partition(par)
        P = PrimarySimilarityClassTypes(par.size() * deg)
        return P(deg, par)

    def coefficient_cycle_type(self, t):
        """
        Returns the coefficient of a cycle type ``t`` in ``self``.

        EXAMPLES::

            sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
            sage: p = SymmetricFunctions(QQ).power()
            sage: CIS = CycleIndexSeriesRing(QQ)
            sage: f = CIS([0, p([1]), 2*p([1,1]),3*p([2,1])])
            sage: f.coefficient_cycle_type([1])
            1
            sage: f.coefficient_cycle_type([1,1])
            2
            sage: f.coefficient_cycle_type([2,1])
            3
        """
        t = Partition(t)
        p = self.coefficient(t.size())
        return p.coefficient(t)

    def count(self, t):
        """
        Return the number of structures corresponding to a certain cycle
        type ``t``.

        EXAMPLES::

            sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
            sage: p = SymmetricFunctions(QQ).power()
            sage: CIS = CycleIndexSeriesRing(QQ)
            sage: f = CIS([0, p([1]), 2*p([1,1]), 3*p([2,1])])
            sage: f.count([1])
            1
            sage: f.count([1,1])
            4
            sage: f.count([2,1])
            6
        """
        t = Partition(t)
        return t.aut() * self.coefficient_cycle_type(t)

def marking_iterator(profile,left=None,standard=False):
    r"""
    Returns the marked profile associated to a partition

    EXAMPLES::

        sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
        sage: p = Partition([3,2,2])
        sage: list(rcc.marking_iterator(p))
        [(1, 2, 0),
         (1, 2, 1),
         (1, 3, 0),
         (1, 3, 1),
         (1, 3, 2),
         (2, 2, 2),
         (2, 2, 3),
         (2, 3, 2)]
    """
    e = Partition(sorted(profile,reverse=True)).to_exp_dict()

    if left is not None:
        assert(left in e)

    if left is not None: keys = [left]
    else: keys = e.keys()

    for m in keys:
        if standard: angles = range(1,m-1)
        else: angles = range(0,m)
        for a in angles:
            yield (1,m,a)

    for m_l in keys:
        for m_r in e:
            if m_l != m_r or e[m_l] > 1:
                yield (2,m_l,m_r)

def q_subgroups_of_abelian_group(la, mu, q=None, algorithm='birkhoff'):
    r"""
    Return the `q`-number of subgroups of type ``mu`` in a finite abelian
    group of type ``la``.

    INPUT:

    - ``la`` -- type of the ambient group as a :class:`Partition`
    - ``mu`` -- type of the subgroup as a :class:`Partition`
    - ``q`` -- (default: ``None``) an indeterminat or a prime number; if
      ``None``, this defaults to `q \in \ZZ[q]`
    - ``algorithm`` -- (default: ``'birkhoff'``) the algorithm to use can be
      one of the following:

      - ``'birkhoff`` -- use the Birkhoff formula from [Bu87]_
      - ``'delsarte'`` -- use the formula from [Delsarte48]_

    OUTPUT:

    The number of subgroups of type ``mu`` in a group of type ``la`` as a
    polynomial in ``q``.

    ALGORITHM:

    Let `q` be a prime number and `\lambda = (\lambda_1, \ldots, \lambda_l)`
    be a partition. A finite abelian `q`-group is of type `\lambda` if it
    is isomorphic to

    .. MATH::

        \ZZ / q^{\lambda_1} \ZZ \times \cdots \times \ZZ / q^{\lambda_l} \ZZ.

    The formula from [Bu87]_ works as follows:
    Let `\lambda` and `\mu` be partitions. Let `\lambda^{\prime}` and
    `\mu^{\prime}` denote the conjugate partitions to `\lambda` and `\mu`,
    respectively. The number of subgroups of type `\mu` in a group of type
    `\lambda` is given by

    .. MATH::

        \prod_{i=1}^{\mu_1} q^{\mu^{\prime}_{i+1}
        (\lambda^{\prime}_i - \mu^{\prime}_i)}
        \binom{\lambda^{\prime}_i - \mu^{\prime}_{i+1}}
        {\mu^{\prime}_i - \mu^{\prime}_{i+1}}_q

    The formula from [Delsarte48]_ works as follows:
    Let `\lambda` and `\mu` be partitions. Let `(s_1, s_2, \ldots, s_l)`
    and `(r_1, r_2, \ldots, r_k)` denote the parts of the partitions
    conjugate to `\lambda` and `\mu` respectively. Let


    .. MATH::

        \mathfrak{F}(\xi_1, \ldots, \xi_k) = \xi_1^{r_2} \xi_2^{r_3} \cdots
        \xi_{k-1}^{r_k} \prod_{i_1=r_2}^{r_1-1} (\xi_1-q^{i_1})
        \prod_{i_2=r_3}^{r_2-1} (\xi_2-q^{i_2}) \cdots
        \prod_{i_k=0}^{r_k-1} (\xi_k-q^{-i_k}).

    Then the number of subgroups of type `\mu` in a group of type `\lambda`
    is given by

    .. MATH::

        \frac{\mathfrak{F}(q^{s_1}, q^{s_2}, \ldots, q^{s_k})}{\mathfrak{F}
        (q^{r_1}, q^{r_2}, \ldots, q^{r_k})}.

    EXAMPLES::

        sage: from sage.combinat.q_analogues import q_subgroups_of_abelian_group
        sage: q_subgroups_of_abelian_group([1,1], [1])
        q + 1
        sage: q_subgroups_of_abelian_group([3,3,2,1], [2,1])
        q^6 + 2*q^5 + 3*q^4 + 2*q^3 + q^2
        sage: R.<t> = QQ[]
        sage: q_subgroups_of_abelian_group([5,3,1], [3,1], t)
        t^4 + 2*t^3 + t^2
        sage: q_subgroups_of_abelian_group([5,3,1], [3,1], 3)
        144
        sage: q_subgroups_of_abelian_group([1,1,1], [1]) == q_subgroups_of_abelian_group([1,1,1], [1,1])
        True
        sage: q_subgroups_of_abelian_group([5], [3])
        1
        sage: q_subgroups_of_abelian_group([1], [2])
        0
        sage: q_subgroups_of_abelian_group([2], [1,1])
        0

    TESTS:

    Check the same examples with ``algorithm='delsarte'``::

        sage: q_subgroups_of_abelian_group([1,1], [1], algorithm='delsarte')
        q + 1
        sage: q_subgroups_of_abelian_group([3,3,2,1], [2,1], algorithm='delsarte')
        q^6 + 2*q^5 + 3*q^4 + 2*q^3 + q^2
        sage: q_subgroups_of_abelian_group([5,3,1], [3,1], t, algorithm='delsarte')
        t^4 + 2*t^3 + t^2
        sage: q_subgroups_of_abelian_group([5,3,1], [3,1], 3, algorithm='delsarte')
        144
        sage: q_subgroups_of_abelian_group([1,1,1], [1], algorithm='delsarte') == q_subgroups_of_abelian_group([1,1,1], [1,1])
#.........这里部分代码省略.........

def is_gale_ryser(r,s):
    r"""
    Tests whether the given sequences satisfy the condition
    of the Gale-Ryser theorem.

    Given a binary matrix `B` of dimension `n\times m`, the
    vector of row sums is defined as the vector whose
    `i^{\mbox{th}}` component is equal to the sum of the `i^{\mbox{th}}`
    row in `A`. The vector of column sums is defined similarly.

    If, given a binary matrix, these two vectors are easy to compute,
    the Gale-Ryser theorem lets us decide whether, given two
    non-negative vectors `r,s`, there exists a binary matrix
    whose row/colum sums vectors are `r` and `s`.

    This functions answers accordingly.

    INPUT:

    - ``r``, ``s`` -- lists of non-negative integers.

    ALGORITHM:

    Without loss of generality, we can assume that:

    - The two given sequences do not contain any `0` ( which would
      correspond to an empty column/row )

    - The two given sequences are ordered in decreasing order
      (reordering the sequence of row (resp. column) sums amounts to
      reordering the rows (resp. columns) themselves in the matrix,
      which does not alter the columns (resp. rows) sums.

    We can then assume that `r` and `s` are partitions
    (see the corresponding class ``Partition``)

    If `r^*` denote the conjugate of `r`, the Gale-Ryser theorem
    asserts that a binary Matrix satisfying the constraints exists
    if and only if `s\preceq r^*`, where `\preceq` denotes
    the domination order on partitions.

    EXAMPLES::

        sage: from sage.combinat.integer_vector import is_gale_ryser
        sage: is_gale_ryser([4,2,2],[3,3,1,1])
        True
        sage: is_gale_ryser([4,2,1,1],[3,3,1,1])
        True
        sage: is_gale_ryser([3,2,1,1],[3,3,1,1])
        False

    REMARK: In the literature, what we are calling a
    Gale-Ryser sequence sometimes goes by the (rather
    generic-sounding) term ''realizable sequence''.
    """

    # The sequences only contan non-negative integers
    if [x for x in r if x<0] or [x for x in s if x<0]:
        return False

    # builds the corresponding partitions, i.e.
    # removes the 0 and sorts the sequences
    from sage.combinat.partition import Partition
    r2 = Partition(sorted([x for x in r if x>0], reverse=True))
    s2 = Partition(sorted([x for x in s if x>0], reverse=True))

    # If the two sequences only contained zeroes
    if len(r2) == 0 and len(s2) == 0:
        return True

    rstar = Partition(r2).conjugate()

    #                                same number of 1s           domination
    return len(rstar) <= len(s2) and  sum(r2) == sum(s2) and rstar.dominates(s)

def _gamma_irr_rec(p, marking):
    r"""
    Internal recursive function called by :func:`gamma_irr`
    """
    if len(p) == 0:
        return 1

    if marking[0] == 1:
        m = marking[1]
        a = marking[2]
        i = p.index(m)
        pp = Partition(p._list[:i]+p._list[i+1:]) # the partition p'

        N = gamma_std(pp._list + [m+2],(1,m+2,m-a))

        for m1 in xrange(1,m-1):
            m2 = m-m1-1
            for a1 in xrange(max(0,a-m2),min(a,m1)):
                a2 = a - a1 - 1
                for p1,p2 in bidecompositions(pp):
                    l1 = sorted([m1]+p1._list,reverse=True)
                    l2 = sorted([m2+2]+p2._list,reverse=True)
                    if (sum(l1)+len(l1)) % 2 == 0 and (sum(l2)+len(l2)) % 2 == 0:
                        N -= (_gamma_irr_rec(Partition(l1), (1,m1,a1)) *
                              gamma_std(Partition(l2),(1,m2+2,m2-a2)))
        return N


    elif marking[0] == 2:
        m1 = marking[1]
        m2 = marking[2]
        i1 = p.index(m1)
        i2 = p.index(m2)
        if m1 == m2: i2 += 1
        if i2 < i1: i1,i2 = i2,i1
        pp = Partition(p._list[:i1] + p._list[i1+1:i2] + p._list[i2+1:])

        N = gamma_std(pp._list + [m1+1,m2+1],(2,m1+1,m2+1))

        for p1,p2 in bidecompositions(pp):
            for k1 in xrange(1,m1): # remove (m'_1|.) (m''_1 o m_2)
                k2 = m1-k1-1
                l1 = sorted(p1._list+[k1],reverse=True)
                l2 = sorted(p2._list+[k2+1,m2+1],reverse=True)
                if (sum(l1)+len(l1)) %2 == 0 and (sum(l2)+len(l2)) %2 == 0:
                    for a in xrange(k1): # a is an angle
                        N -= (_gamma_irr_rec(Partition(l1), (1,k1,a))*
                              gamma_std(Partition(l2),(2,k2+1,m2+1)))

            for k1 in xrange(1,m2): # remove (m_1 o m'_2) (m''_2|.)
                k2 = m2-k1-1
                l1 = sorted(p1._list+[m1,k1],reverse=True)
                l2 = sorted(p2._list+[k2+2],reverse=True)
                if (sum(l1)+len(l1)) %2 == 0 and (sum(l2)+len(l2)) %2 == 0:
                    for a in xrange(1,k2+1): # a is an angle for standard perm
                        N -= (_gamma_irr_rec(Partition(l1), (2,m1,k1)) *
                              gamma_std(Partition(l2),(1,k2+2,a)))

        for m in pp.to_exp_dict(): # remove (m_1, k_1) (k_2, m_2) for k1+k2+1 an other zero
            q = pp._list[:]
            del q[q.index(m)]
            for p1,p2 in bidecompositions(Partition(q)):
                for k1 in xrange(1,m):
                    k2 = m-k1-1
                    l1 = sorted(p1._list+[m1,k1],reverse=True)
                    l2 = sorted(p2._list+[k2+1,m2+1],reverse=True)
                    if (sum(l1)+len(l1))%2 == 0 and (sum(l2)+len(l2))%2 == 0:
                        N -= (_gamma_irr_rec(Partition(l1), (2,m1,k1)) *
                              gamma_std(Partition(l2),(2,k2+1,m2+1)))

        return N

    else:
        raise ValueError, "marking must be a 3-tuple of the form (1,m,a) or (2,m1,m2)"

def _delta_irr_rec(p, marking):
    r"""
    Internal recursive function called by :func:`delta_irr`.
    """
    if len(p) == 0:
        return 0

    if marking[0] == 1:
        m = marking[1]
        a = marking[2]
        i = p.index(m)
        pp = Partition(p._list[:i]+p._list[i+1:]) # the partition p'

        N = (-1)**a* delta_std(
                pp._list + [m+2],
                (1,m+2,m-a))

        for m1 in xrange(1,m-1,2):
            m2 = m-m1-1
            for a1 in xrange(max(0,a-m2),min(a,m1)):
                a2 = a - a1 - 1
                for p1,p2 in bidecompositions(pp):
                    l1 = sorted([m1]+p1._list,reverse=True)
                    l2 = sorted([m2+2]+p2._list,reverse=True)
                    N += (-1)**a2*(_delta_irr_rec(Partition(l1),(1,m1,a1)) *
                        spin_difference_for_standard_permutations(Partition(l2),(1,m2+2,m2-a2)))
        return N

    elif marking[0] == 2:
        m1 = marking[1]
        m2 = marking[2]
        i1 = p.index(m1)
        i2 = p.index(m2)
        if m1 == m2: i2 += 1
        if i2 < i1: i1,i2 = i2,i1
        pp = Partition(p._list[:i1] + p._list[i1+1:i2] + p._list[i2+1:])

        N = d(Partition(sorted(pp._list+[m1+m2+1],reverse=True))) /  pp.centralizer_size()
        # nb of standard permutations that corrresponds to extension of good
        # guys

        for p1,p2 in bidecompositions(Partition(pp)):
            for k1 in xrange(1,m1,2): # remove (k1|.) (k2 o m_2)
                k2 = m1-k1-1
                q1 = Partition(sorted(p1._list+[k1],reverse=True))
                q2 = Partition(sorted(p2._list+[k2+m2+1],reverse=True))
                for a in xrange(k1): # a is a angle
                    N += _delta_irr_rec(q1, (1,k1,a)) * d(q2) / p2.centralizer_size()

            for k1 in xrange(1,m2,2): # remove (m_1 o k1) (k2|.)
                k2 = m2-k1-1
                l1 = sorted(p1._list+[m1,k1],reverse=True)
                l2 = sorted(p2._list+[k2+2],reverse=True)
                for a in xrange(1,k2+1): # a is an angle for standard perm
                    N += (_delta_irr_rec(Partition(l1), (2,m1,k1)) *
                        spin_difference_for_standard_permutations(Partition(l2), (1,k2+2,a)))

        for m in pp.to_exp_dict(): # remove (m_1 o k_1) (k_2 o m_2) for k1+k2+1 an other zero
            q = pp._list[:]
            del q[q.index(m)]
            for p1,p2 in bidecompositions(Partition(q)):
                for k1 in xrange(1,m,2):
                    k2 = m-k1-1
                    q1 = Partition(sorted(p1._list+[m1,k1],reverse=True))
                    q2 = Partition(sorted(p2._list+[k2+m2+1],reverse=True))
                    N += _delta_irr_rec(q1, (2,m1,k1)) * d(q2) / p2.centralizer_size()

        return N

class SymmetricGroupRepresentation_generic_class(SageObject):
    r"""
    Generic methods for a representation of the symmetric group.
    """
    _default_ring = None

    def __init__(self, partition, ring=None, cache_matrices=True):
        r"""
        An irreducible representation of the symmetric group corresponding
        to ``partition``.

        For more information, see the documentation for
        :func:`SymmetricGroupRepresentation`.

        EXAMPLES::

            sage: spc = SymmetricGroupRepresentation([3])
            sage: spc([3,2,1])
            [1]
            sage: spc == loads(dumps(spc))
            True

            sage: spc = SymmetricGroupRepresentation([3], cache_matrices=False)
            sage: spc([3,2,1])
            [1]
            sage: spc == loads(dumps(spc))
            True
        """
        self._partition = Partition(partition)
        self._ring = ring if not ring is None else self._default_ring
        if cache_matrices is False:
            self.representation_matrix = self._representation_matrix_uncached

    def __eq__(self, other):
        r"""
        Test for equality.

        EXAMPLES::

            sage: spc1 = SymmetricGroupRepresentation([3], cache_matrices=True)
            sage: spc1([3,1,2])
            [1]
            sage: spc2 = loads(dumps(spc1))
            sage: spc1 == spc2
            True

        ::

            sage: spc3 = SymmetricGroupRepresentation([3], cache_matrices=False)
            sage: spc3([3,1,2])
            [1]
            sage: spc4 = loads(dumps(spc3))
            sage: spc3 == spc4
            True

        TESTS:

        The following tests against some bug that was fixed in :trac:`8611`::

            sage: spc = SymmetricGroupRepresentation([3])
            sage: spc.important_info = 'Sage rules'
            sage: spc == SymmetricGroupRepresentation([3])
            True

        """
        if not isinstance(other, type(other)):
            return False
        return (self._ring,self._partition)==(other._ring,other._partition)
#        # both self and other must have caching enabled
#        if 'representation_matrix' in self.__dict__:
#            if 'representation_matrix' not in other.__dict__:
#                return False
#            else:
#                for key in self.__dict__:
#                    if key != 'representation_matrix':
#                        if self.__dict__[key] != other.__dict__[key]:
#                            return False
#                else:
#                    return True
#        else:
#            if 'representation_matrix' in other.__dict__:
#                return False
#            else:
#                return self.__dict__.__eq__(other.__dict__)

    def __call__(self, permutation):
        r"""
        Return the image of ``permutation`` in the representation.

        EXAMPLES::

            sage: spc = SymmetricGroupRepresentation([2,1])
            sage: spc([1,3,2])
            [ 1  0]
            [ 1 -1]
        """
        return self.representation_matrix(Permutation(permutation))

    def __iter__(self):
        r"""
#.........这里部分代码省略.........

#.........这里部分代码省略.........
        27664
        sage: T = crystals.HighestWeight(La[6])
        sage: T.cardinality()
        1539
        sage: T = crystals.HighestWeight(La[7])
        sage: T.cardinality()
        56

    An example with an affine type::

        sage: C = CartanType(['C',2,1])
        sage: La = C.root_system().weight_lattice().fundamental_weights()
        sage: T = crystals.HighestWeight(La[1])
        sage: sorted(T.subcrystal(max_depth=3), key=str)
        [(-Lambda[0] + 3*Lambda[1] - Lambda[2] - delta,),
         (-Lambda[0] + Lambda[1] + Lambda[2] - delta,),
         (-Lambda[1] + 2*Lambda[2] - delta,),
         (2*Lambda[0] - Lambda[1],),
         (Lambda[0] + Lambda[1] - Lambda[2],),
         (Lambda[0] - Lambda[1] + Lambda[2],),
         (Lambda[1],)]

    Using the various models::

        sage: La = RootSystem(['F',4]).weight_lattice().fundamental_weights()
        sage: wt = La[1] + La[4]
        sage: crystals.HighestWeight(wt)
        The crystal of LS paths of type ['F', 4] and weight Lambda[1] + Lambda[4]
        sage: crystals.HighestWeight(wt, model='NakajimaMonomials')
        Highest weight crystal of modified Nakajima monomials of
         Cartan type ['F', 4] and highest weight Lambda[1] + Lambda[4]
        sage: crystals.HighestWeight(wt, model='AlcovePaths')
        Highest weight crystal of alcove paths of type ['F', 4] and weight Lambda[1] + Lambda[4]
        sage: crystals.HighestWeight(wt, model='RiggedConfigurations')
        Crystal of rigged configurations of type ['F', 4] and weight Lambda[1] + Lambda[4]
    """
    cartan_type = dominant_weight.parent().cartan_type()
    if model is None:
        if cartan_type.is_finite():
            if cartan_type.type() == 'E':
                model = 'TypeE'
            elif cartan_type.type() in ['A','B','C','D','G']:
                model = 'Tableaux'
            else:
                model = 'LSPaths'
        else:
            model = 'LSPaths'

    if model == 'Tableaux':
        sh = sum([[i]*c for i,c in dominant_weight], [])
        sh = Partition(reversed(sh))
        return CrystalOfTableaux(cartan_type, shape=sh.conjugate())

    if model == 'TypeE':
        if not cartan_type.is_finite() or cartan_type.type() != 'E':
            raise ValueError("only for finite type E")
        if cartan_type.rank() == 6:
            return FiniteDimensionalHighestWeightCrystal_TypeE6(dominant_weight)
        elif cartan_type.rank() == 7:
            return FiniteDimensionalHighestWeightCrystal_TypeE7(dominant_weight)
        raise NotImplementedError

    if model == 'NakajimaMonomials':
        # Make sure it's in the weight lattice
        P = dominant_weight.parent().root_system.weight_lattice()
        wt = P.sum_of_terms((i, c) for i,c in dominant_weight)
        return CrystalOfNakajimaMonomials(cartan_type, wt)

    if model == 'LSPaths':
        # Make sure it's in the (extended) weight space
        if cartan_type.is_affine():
            P = dominant_weight.parent().root_system.weight_space(extended=True)
        else:
            P = dominant_weight.parent().root_system.weight_space()
        wt = P.sum_of_terms((i, c) for i,c in dominant_weight)
        return CrystalOfLSPaths(wt)

    if model == 'AlcovePaths':
        # Make sure it's in the weight space
        P = dominant_weight.parent().root_system.weight_space()
        wt = P.sum_of_terms((i, c) for i,c in dominant_weight)
        return CrystalOfAlcovePaths(wt, highest_weight_crystal=True)

    if model == 'GeneralizedYoungWalls':
        if not cartan_type.is_affine():
            raise ValueError("only for affine types")
        if cartan_type.type() != 'A':
            raise NotImplementedError("only for affine type A")
        # Make sure it's in the weight lattice
        P = dominant_weight.parent().root_system.weight_space()
        wt = P.sum_of_terms((i, c) for i,c in dominant_weight)
        return CrystalOfGeneralizedYoungWalls(cartan_type.rank(), wt)

    if model == 'RiggedConfigurations':
        # Make sure it's in the weight lattice
        P = dominant_weight.parent().root_system.weight_lattice()
        wt = P.sum_of_terms((i, c) for i,c in dominant_weight)
        return CrystalOfRiggedConfigurations(cartan_type, wt)

    raise ValueError("invalid model")

def insertion_tableau(skp, perm, evaluation, tableau, length):
    """
    INPUT:

    -  ``skp`` -- skew partitions

    -  ``perm, evaluation`` -- non-negative integers

    -  ``tableau`` -- skew tableau

    -  ``length`` -- integer

    TESTS::

        sage: from sage.combinat.ribbon_tableau import insertion_tableau
        sage: insertion_tableau([[1], []], [1], 1, [[], []], 1)
        [[], [[1]]]
        sage: insertion_tableau([[2, 1], []], [1, 1], 2, [[], [[1]]], 1)
        [[], [[2], [1, 2]]]
        sage: insertion_tableau([[2, 1], []], [0, 0], 3, [[], [[2], [1, 2]]], 1)
        [[], [[2], [1, 2]]]
        sage: insertion_tableau([[1, 1], []], [1], 2, [[], [[1]]], 1)
        [[], [[2], [1]]]
        sage: insertion_tableau([[2], []], [0, 1], 2, [[], [[1]]], 1)
        [[], [[1, 2]]]
        sage: insertion_tableau([[2, 1], []], [0, 1], 3, [[], [[2], [1]]], 1)
        [[], [[2], [1, 3]]]
        sage: insertion_tableau([[1, 1], []], [2], 1, [[], []], 2)
        [[], [[1], [0]]]
        sage: insertion_tableau([[2], []], [2, 0], 1, [[], []], 2)
        [[], [[1, 0]]]
        sage: insertion_tableau([[2, 2], []], [0, 2], 2, [[], [[1], [0]]], 2)
        [[], [[1, 2], [0, 0]]]
        sage: insertion_tableau([[2, 2], []], [2, 0], 2, [[], [[1, 0]]], 2)
        [[], [[2, 0], [1, 0]]]
        sage: insertion_tableau([[2, 2], [1]], [3, 0], 1, [[], []], 3)
        [[1], [[1, 0], [0]]]
    """
    psave = Partition(skp[1])
    partc = skp[1] + [0]*(len(skp[0])-len(skp[1]))

    tableau = SkewTableau(expr=tableau).to_expr()[1]

    for k in range(len(tableau)):
        tableau[-(k+1)] += [0]* ( skp[0][k] - partc[k] - len(tableau[-(k+1)]))

    ## We construct a tableau from the southwest corner to the northeast one
    tableau = [[0] * (skp[0][k] - partc[k])
               for k in reversed(range(len(tableau), len(skp[0])))] + tableau

    tableau = SkewTableaux().from_expr([skp[1], tableau]).conjugate()
    tableau = tableau.to_expr()[1]

    skp = SkewPartition(skp).conjugate().to_list()
    skp[1].extend( [0]*(len(skp[0])-len(skp[1])) )

    if len(perm) > len(skp[0]):
        return None

    for k in range(len(perm)):
        if perm[ -(k+1) ] !=0:
            tableau[len(tableau)-len(perm)+k][ skp[0][len(perm)-(k+1)] - skp[1][ len(perm)-(k+1) ] - 1 ] = evaluation

    return SkewTableau(expr=[psave.conjugate(),tableau]).conjugate().to_expr()

#.........这里部分代码省略.........

        \begin{aligned}
        m_1 & = l_1 - r + 2r_1 - r_2,
        \\ m_2 & = l_2 - r_1 + 2r_2 - r_3,
        \\ & \vdots ,
        \\ m_{n-1} & = l_{n-1} - r_{n-2} + 2r_{n-1} - r_n,
        \\ m_n & = l_n - r_{n-1} + r_n
        \end{aligned}

    and solving for `r_i` and back substituting we obtain the equations:

    .. MATH::

        \begin{aligned}
        r_n & = r_{n-1} + m_n - l_n,
        \\ r_{n-1} & = r_{n-2} + m_{n-1} - l_{n-1} + m_n - l_n,
        \\ & \vdots ,
        \\ r_1 & = r + \sum_{k=1}^n (m_k - l_k),
        \end{aligned}

    or in general we have the recursive equation:

    .. MATH::

        r_i = r_{i-1} + \sum_{k=i}^n (m_k - l_k).

    This, combined with the condition that `r_0 = r`, determines the
    `r_i` uniquely (recursively). Next we define

    .. MATH::

        t = (r_{n-2} - r_{n-1})(l_n - r_{n-1})
        + (r_{n-3} - r_{n-2})(l_{n-1} + l_n - r_{n-2}) + \cdots
        + (r_0 - r_1)(l_2 + \cdots + l_n - r_1),

    and with these notations we have

    .. MATH::

        P^{\nu}_{\mu,(1^r)} = q^t \binom{l_n}{r_{n-1}}_q
        \binom{l_{n-1}}{r_{n-2} - r_{n-1}}_q \cdots \binom{l_1}{r_0 - r_1}_q.

    To compute `P^{\nu}_{\mu,\lambda}` in general, we compute the product
    `I_{\mu} I_{\lambda}` in the Hall algebra and return the coefficient of
    `I_{\nu}`.

    EXAMPLES::

        sage: from sage.combinat.hall_polynomial import hall_polynomial
        sage: hall_polynomial([1,1],[1],[1])
        q + 1
        sage: hall_polynomial([2],[1],[1])
        1
        sage: hall_polynomial([2,1],[2],[1])
        q
        sage: hall_polynomial([2,2,1],[2,1],[1,1])
        q^2 + q
        sage: hall_polynomial([2,2,2,1],[2,2,1],[1,1])
        q^4 + q^3 + q^2
        sage: hall_polynomial([3,2,2,1], [3,2], [2,1])
        q^6 + q^5
        sage: hall_polynomial([4,2,1,1], [3,1,1], [2,1])
        2*q^3 + q^2 - q - 1
        sage: hall_polynomial([4,2], [2,1], [2,1], 0)
        1
    """
    if q is None:
        q = ZZ['q'].gen()
    R = q.parent()

    # Make sure they are partitions
    nu = Partition(nu)
    mu = Partition(mu)
    la = Partition(la)

    if sum(nu) != sum(mu) + sum(la):
        return R.zero()

    if all(x == 1 for x in la):
        r = [len(la)]   # r will be [r_0, r_1, ..., r_n].
        exp_nu = nu.to_exp()  # exp_nu == [l_1, l_2, ..., l_n].
        exp_mu = mu.to_exp()  # exp_mu == [m_1, m_2, ..., m_n].
        n = max(len(exp_nu), len(exp_mu))
        for k in range(n):
            r.append(r[-1] + sum(exp_mu[k:]) - sum(exp_nu[k:]))
        # Now, r is [r_0, r_1, ..., r_n].
        exp_nu += [0]*(n - len(exp_nu)) # Pad with 0's until it has length n
        # Note that all -1 for exp_nu is due to indexing
        t = sum((r[k-2] - r[k-1])*(sum(exp_nu[k-1:]) - r[k-1]) for k in range(2,n+1))
        if t < 0:
            # This case needs short-circuiting, since otherwise q**-t
            # might throw an exception if q is non-invertible.
            return R.zero()
        return q**t * q_binomial(exp_nu[n-1], r[n-1], q) \
               * prod([q_binomial(exp_nu[k-1], r[k-1] - r[k], q)
                       for k in range(1, n)], R.one())

    from sage.algebras.hall_algebra import HallAlgebra
    H = HallAlgebra(R, q)
    return (H[mu]*H[la]).coefficient(nu)