def K_k_Schur_non_commutative_variables(self,la):
        r"""
        Returns the K-`k`-Schur function, as embedded inside the affine zero Hecke algebra.

        INPUT:

        - ``la`` -- A `k`-bounded Partition

        OUTPUT:

        - An element of the affine zero Hecke algebra.

        EXAMPLES::

            sage: g = SymmetricFunctions(QQ).kBoundedSubspace(3,1).K_kschur()
            sage: g.K_k_Schur_non_commutative_variables([2,1])
            T3*T1*T0 + T1*T2*T0 + T3*T2*T0 - T2*T0 + T0*T1*T0 + T2*T0*T1 + T0*T3*T0 + T2*T0*T3 + T0*T3*T1 + T2*T3*T2 - T3*T1 + T2*T3*T1 + T3*T1*T2 + T1*T2*T1
            sage: g.K_k_Schur_non_commutative_variables([])
            1
            sage: g.K_k_Schur_non_commutative_variables([4,1])
            Traceback (most recent call last):
            ...
            ValueError: Partition should be 3-bounded
        """
        SF = SymmetricFunctions(self.base_ring())
        h = SF.h()
        S = h(self._g_to_kh_on_basis(la)).support()
        return sum(h(self._g_to_kh_on_basis(la)).coefficient(x)*self.homogeneous_basis_noncommutative_variables_zero_Hecke(x) for x in S)

    def __init__(self, R):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: NCSymD1 = SymmetricFunctionsNonCommutingVariablesDual(FiniteField(23))
            sage: NCSymD2 = SymmetricFunctionsNonCommutingVariablesDual(Integers(23))
            sage: TestSuite(SymmetricFunctionsNonCommutingVariables(QQ).dual()).run()
        """
        # change the line below to assert(R in Rings()) once MRO issues from #15536, #15475 are resolved
        assert(R in Fields() or R in Rings()) # side effect of this statement assures MRO exists for R
        self._base = R # Won't be needed once CategoryObject won't override base_ring
        category = GradedHopfAlgebras(R)  # TODO: .Commutative()
        Parent.__init__(self, category=category.WithRealizations())

        # Bases
        w = self.w()

        # Embedding of Sym in the homogeneous bases into DNCSym in the w basis
        Sym = SymmetricFunctions(self.base_ring())
        Sym_h_to_w = Sym.h().module_morphism(w.sum_of_partitions,
                                             triangular='lower',
                                             inverse_on_support=w._set_par_to_par,
                                             codomain=w, category=category)
        Sym_h_to_w.register_as_coercion()
        self.to_symmetric_function = Sym_h_to_w.section()

    def k_schur_noncommutative_variables(self, la):
        r"""
        In type `A^{(1)}` this is the `k`-Schur function in noncommutative variables defined by Thomas Lam.

        REFERENCES:

           .. [Lam2005] T. Lam, Affine Stanley symmetric functions, Amer. J. Math.  128  (2006),  no. 6, 1553--1586.

        This function is currently only defined in type `A^{(1)}`.

        INPUT:

        - ``la`` -- a partition with first part bounded by the rank of the Weyl group

        EXAMPLES::

            sage: A = NilCoxeterAlgebra(WeylGroup(['A',3,1]))
            sage: A.k_schur_noncommutative_variables([2,2])
            u[0,3,1,0] + u[3,1,2,0] + u[1,2,0,1] + u[3,2,0,3] + u[2,0,3,1] + u[2,3,1,2]

        TESTS::

            sage: A = NilCoxeterAlgebra(WeylGroup(['A',3,1]))
            sage: A.k_schur_noncommutative_variables([])
            1

            sage: A.k_schur_noncommutative_variables([1,2])
            Traceback (most recent call last):
            ...
            AssertionError: [1, 2] is not a partition.

            sage: A.k_schur_noncommutative_variables([4,2])
            Traceback (most recent call last):
            ...
            AssertionError: [4, 2] is not a 3-bounded partition.

            sage: C = NilCoxeterAlgebra(WeylGroup(['C',3,1]))
            sage: C.k_schur_noncommutative_variables([2,2])
            Traceback (most recent call last):
            ...
            AssertionError: Weyl Group of type ['C', 3, 1] (as a matrix group acting on the root space) is not affine type A.


        """
        assert self._cartan_type[0] == 'A' and len(self._cartan_type) == 3 and self._cartan_type[2] == 1, "%s is not affine type A."%(self._W)
        assert la in Partitions(), "%s is not a partition."%(la)
        assert (len(la) == 0 or la[0] < self._W.n), "%s is not a %s-bounded partition."%(la, self._W.n-1)
        Sym = SymmetricFunctions(self._base_ring)
        h = Sym.homogeneous()
        ks = Sym.kschur(self._n-1,1)
        f = h(ks[la])
        return sum(f.coefficient(x)*self.homogeneous_noncommutative_variables(x) for x in f.support())

    def __init__(self, w, n, x = None):
        r"""
        EXAMPLES::

            sage: B = crystals.AffineFactorization([[3,2],[2]],4,x=0,k=3)
            Traceback (most recent call last):
            ...
            ValueError: x cannot be in reduced word of s0*s3*s2

            sage: B = crystals.AffineFactorization([[3,2],[2]],4,k=3)
            sage: B.x
            1
            sage: B.w
            s0*s3*s2
            sage: B.k
            3
            sage: B.n
            4

        TESTS::

            sage: W = WeylGroup(['A',3,1], prefix='s')
            sage: w = W.from_reduced_word([2,3,2,1])
            sage: B = crystals.AffineFactorization(w,3)
            sage: TestSuite(B).run()
        """
        Parent.__init__(self, category = ClassicalCrystals())
        self.n = n
        self.k = w.parent().n-1
        self.w = w
        cartan_type = CartanType(['A',n-1])
        self._cartan_type = cartan_type
        from sage.combinat.sf.sf import SymmetricFunctions
        from sage.rings.all import QQ
        Sym = SymmetricFunctions(QQ)
        s = Sym.schur()
        support = s(w.stanley_symmetric_function()).support()
        support = [ [0]*(n-len(mu))+[mu[len(mu)-i-1] for i in range(len(mu))] for mu in support]
        generators = [tuple(p) for mu in support for p in affine_factorizations(w,n,mu)]
        #generators = [tuple(p) for p in affine_factorizations(w, n)]
        self.module_generators = [self(t) for t in generators]
        if x is None:
            if generators != []:
                x = min( set(range(self.k+1)).difference(set(
                            sum([i.reduced_word() for i in generators[0]],[]))))
            else:
                x = 0
        if x in set(w.reduced_word()):
            raise ValueError("x cannot be in reduced word of {}".format(w))
        self.x = x

    def __init__(self, R, k, t=None):
        """
        EXAMPLES::

            sage: kSchurFunctions(QQ, 3).base_ring()
            doctest:1: DeprecationWarning: Deprecation warning: Please use SymmetricFunctions(QQ).kschur() instead!
            See http://trac.sagemath.org/5457 for details.
            Univariate Polynomial Ring in t over Rational Field
            sage: kSchurFunctions(QQ, 3, t=1).base_ring()
            Rational Field
            sage: ks3 = kSchurFunctions(QQ, 3)
            sage: ks3 == loads(dumps(ks3))
            True
        """
        self.k = k
        self._name = "k-Schur Functions at level %s"%k
        self._prefix = "ks%s"%k
        self._element_class = kSchurFunctions_t.Element

        if t is None:
            R = R['t']
            self.t = R.gen()
        elif t not in R:
            raise ValueError, "t (=%s) must be in R (=%s)"%(t,R)
        else:
            self.t = R(t)
            if str(t) != 't':
                self._name += " with t=%s"%self.t

        self._s_to_self_cache = s_to_k_cache.get(k, {})
        self._self_to_s_cache = k_to_s_cache.get(k, {})

        # This is an abuse, since kschur functions do not form a basis of Sym
        from sage.combinat.sf.sf import SymmetricFunctions
        Sym = SymmetricFunctions(R)
        sfa.SymmetricFunctionAlgebra_generic.__init__(self, Sym)
        # so we need to take some counter measures
        self._basis_keys = sage.combinat.partition.Partitions(max_part=k)
        # The following line is just a temporary workaround to keep
        # the repr of those k-schur as they were before #13404; since
        # they are deprecated, there is no need to bother about them.
        self.rename(self._name+" over %s"%self.base_ring())

        self._s = Sym.s()
        # temporary until Hom(GradedHopfAlgebrasWithBasis work better)
        category = sage.categories.all.ModulesWithBasis(self.base_ring())
        # This really should be a conversion, not a coercion (it can fail)
        self   .register_coercion(SetMorphism(Hom(self._s, self, category), self._s_to_self))
        self._s.register_coercion(SetMorphism(Hom(self, self._s, category), self._self_to_s))

 def charpoly(self, g, var='x'):
     r"""
     Determines the characteristic polynomial `\det(I-gT)`
     """
     if self.degree() == 0:
         return QQ.one()
     from sage.combinat.sf.sf import SymmetricFunctions
     S = SymmetricFunctions(QQ)
     p = S.powersum()
     e = S.elementary()
     deg = self.degree()
     traces = [self(g ** n) for n in range(1, deg+1)]
     x = PolynomialRing(QQ, var).gen()
     cp = x ** deg
     for n in range(deg):
         mc = p(e[n+1]).monomial_coefficients()
         cp += (-1) ** (n+1) * x ** (deg-1-n) * sum(mc[k] * prod(traces[j-1] for j in k) for k in mc.keys())
     return cp

    def __init__(self, R):
        """
        The Hopf algebra of quasi-symmetric functions.
        See ``QuasiSymmetricFunctions`` for full documentation.

        EXAMPLES::

            sage: QuasiSymmetricFunctions(QQ)
            Quasisymmetric functions over the Rational Field
            sage: TestSuite(QuasiSymmetricFunctions(QQ)).run()

        """
        assert R in Rings()
        self._base = R # Won't be needed once CategoryObject won't override base_ring
        category = GradedHopfAlgebras(R)  # TODO: .Commutative()
        Parent.__init__(self, category = category.WithRealizations())

        # Bases
        Monomial    = self.Monomial()
        Fundamental = self.Fundamental()
        dualImmaculate = self.dualImmaculate()

        # Change of bases
        Fundamental.module_morphism(Monomial.sum_of_finer_compositions,
                                    codomain=Monomial, category=category
                                    ).register_as_coercion()
        Monomial   .module_morphism(Fundamental.alternating_sum_of_finer_compositions,
                                    codomain=Fundamental, category=category
                                    ).register_as_coercion()
        #This changes dualImmaculate into Monomial
        dualImmaculate.module_morphism(dualImmaculate._to_Monomial_on_basis,
                                          codomain = Monomial, category = category
                                          ).register_as_coercion()
        #This changes Monomial into dualImmaculate
        Monomial.module_morphism(dualImmaculate._from_Monomial_on_basis,
                                          codomain = dualImmaculate, category = category
                                          ).register_as_coercion()
        # Embedding of Sym into QSym in the monomial bases
        Sym = SymmetricFunctions(self.base_ring())
        Sym_m_to_M = Sym.m().module_morphism(Monomial.sum_of_partition_rearrangements,
                                           triangular='upper', inverse_on_support=Monomial._comp_to_par,
                                           codomain=Monomial, category=category)
        Sym_m_to_M.register_as_coercion()
        self.to_symmetric_function = Sym_m_to_M.section()

            def to_symmetric_function( self ):
                r"""
                Takes a quasi-symmetric function, expressed in the monomial basis, and
                returns its symmetric realization, when possible, expressed in the
                monomial basis of symmetric functions.

                OUTPUT:

                - If ``self`` is a symmetric function, then the expansion
                  in the monomial basis of the symmetric functions is returned.
                  Otherwise an error is raised.

                EXAMPLES::

                    sage: QSym = QuasiSymmetricFunctions(QQ)
                    sage: M = QSym.Monomial()
                    sage: (M[3,2] + M[2,3] + M[4,1]).to_symmetric_function()
                    Traceback (most recent call last):
                    ...
                    ValueError: M[2, 3] + M[3, 2] + M[4, 1] is not a symmetric function
                    sage: (M[3,2] + M[2,3] + 2*M[4,1] + 2*M[1,4]).to_symmetric_function()
                    m[3, 2] + 2*m[4, 1]
                    sage: m = SymmetricFunctions(QQ).m()
                    sage: M(m[3,1,1]).to_symmetric_function()
                    m[3, 1, 1]
                    sage: (M(m[2,1])*M(m[2,1])).to_symmetric_function()-m[2,1]*m[2,1]
                    0

                TESTS::

                    sage: (M(0)).to_symmetric_function()
                    0
                    sage: (M([])).to_symmetric_function()
                    m[]
                    sage: (2*M([])).to_symmetric_function()
                    2*m[]

                """
                m = SymmetricFunctions(self.parent().base_ring()).monomial()
                if self.is_symmetric():
                    return m.sum_of_terms([(I, coeff) for (I, coeff) in self
                        if list(I) in Partitions()], distinct=True)
                else:
                    raise ValueError, "%s is not a symmetric function"%self

    def _DualGrothendieck(self,la):
        r"""
        Returns the expansion of the K-`k`-Schur function in the homogeneous basis. This
        method is here for caching purposes.

        INPUT:

        - ``la`` -- A `k`-bounded partition.

        OUTPUT:

        - A symmetric function in the homogeneous basis.

        EXAMPLES::

            sage: g = SymmetricFunctions(QQ).kBoundedSubspace(3,1).K_kschur()
            sage: g._DualGrothendieck(Partition([2,1]))
            h[2] + h[2, 1] - h[3]
            sage: g._DualGrothendieck(Partition([]))
            h[]
            sage: g._DualGrothendieck(Partition([4,1]))
            0
        """
        m = la.size()
        h = SymmetricFunctions(self.base_ring()).h()
        M = self._DualGrothMatrix(m)
        vec = []
        for i in range(m+1):
            for x in Partitions(m-i, max_part=self.k):
                if x == la:
                    vec.append(1)
                else:
                    vec.append(0)
        from sage.modules.free_module_element import vector
        vec = vector(vec)
        sol = M.solve_right(vec)
        new_function = h.zero()
        count = 0
        for i in range(m+1):
            for x in Partitions(m-i, max_part=self.k):
                new_function+= h(x) * sol[count]
                count += 1
        return new_function

    def _DualGrothMatrix(self, m):
        r"""
        Returns the change of basis matrix between the K_kschur basis and the `k`-bounded
        homogeneous basis.

        INPUT:

        - ``m`` -- An integer

        OUTPUT:

        - A matrix.

        EXAMPLES::

            sage: g = SymmetricFunctions(QQ).kBoundedSubspace(3,1).K_kschur()
            sage: g._DualGrothMatrix(3)
            [ 1  1  1  0  0  0  0]
            [ 0  1  2  0  0  0  0]
            [ 0  0  1  0  0  0  0]
            [ 0 -1 -2  1  1  0  0]
            [ 0  0 -2  0  1  0  0]
            [ 0  0  1  0 -1  1  0]
            [ 0  0  0  0  0  0  1]
            sage: g._DualGrothMatrix(0)
            [1]
        """
        new_mat = []
        Sym = SymmetricFunctions(self.base_ring())
        Q = Sym.kBoundedQuotient(self.k,t=1)
        mon = Q.km()
        G = Q.AffineGrothendieckPolynomial
        for i in range(m+1):
            for x in Partitions(m-i, max_part = self.k):
                f =  mon(G(x,m))
                vec = []
                for j in range(m+1):
                    for y in Partitions(m-j, max_part = self.k):
                        vec.append(f.coefficient(y))
                new_mat.append(vec)
        from sage.matrix.constructor import Matrix
        return Matrix(new_mat)

            def to_symmetric_function(self):
                r"""
                Return the image of ``self`` under the natural projection
                map to `Sym`.

                The natural projection map `FSym \to Sym` sends each
                standard tableau `t` to the Schur function `s_\lambda`,
                where `\lambda` is the shape of `t`.
                This map is a surjective Hopf algebra homomorphism.

                EXAMPLES::

                    sage: FSym = algebras.FSym(QQ)
                    sage: G = FSym.G()
                    sage: t = StandardTableau([[1,3],[2,4],[5]])
                    sage: G[t].to_symmetric_function()
                    s[2, 2, 1]
                """
                s = SymmetricFunctions(self.parent().base_ring()).s()
                return s.sum_of_terms((t.shape(), coeff) for t, coeff in self)

 def charpoly_reverse(self, g, var='x'):
     r"""
     Determines the characteristic polynomial `\det(I-gT)`
     
     sage: from sage.rings.number_field.galois_group import GaloisGroup_v3
     sage: from sage.rings.number_field.artin_representation import ArtinRepresentation
     sage: K = NumberField(x^3 - 2, 'a')
     sage: G = GaloisGroup_v3(K, names='b2')
     sage: chi = ArtinRepresentation(G, [2, 0, -1])
     sage: L = G.splitting_field()
     sage: for p in prime_range(5, 50):
     ...    print p, chi.charpoly_reverse(G.artin_symbol(L.primes_above(p)[0]))
     5 -x^2 + 1
     7 x^2 + x + 1
     11 -x^2 + 1
     13 x^2 + x + 1
     17 -x^2 + 1
     19 x^2 + x + 1
     23 -x^2 + 1
     29 -x^2 + 1
     31 x^2 - 2*x + 1
     37 x^2 + x + 1
     41 -x^2 + 1
     43 x^2 - 2*x + 1
     47 -x^2 + 1
     """
     if self.degree() == 0:
         return QQ.one()
     from sage.combinat.sf.sf import SymmetricFunctions
     S = SymmetricFunctions(QQ)
     p = S.powersum()
     e = S.elementary()
     deg = self.degree()
     traces = [self(g ** n) for n in range(1, deg+1)]
     x = PolynomialRing(QQ, var).gen()
     cp = QQ.one()
     for n in range(deg):
         mc = p(e[n+1]).monomial_coefficients()
         cp += (-1) ** (n+1) * x ** (n+1) * sum(mc[k] * prod(traces[j-1] for j in k) for k in mc.keys())
     return cp

    def __init__(self, R):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: TestSuite(SymmetricFunctionsNonCommutingVariables(QQ).dual()).run()
        """
        self._base = R  # Won't be needed once CategoryObject won't override base_ring
        category = GradedHopfAlgebras(R)  # TODO: .Commutative()
        Parent.__init__(self, category=category.WithRealizations())

        # Bases
        w = self.w()

        # Embedding of Sym in the homogeneous bases into DNCSym in the w basis
        Sym = SymmetricFunctions(self.base_ring())
        Sym_h_to_w = Sym.h().module_morphism(
            w.sum_of_partitions, triangular="lower", inverse_on_support=w._set_par_to_par, codomain=w, category=category
        )
        Sym_h_to_w.register_as_coercion()
        self.to_symmetric_function = Sym_h_to_w.section()

            def to_symmetric_function(self):
                r"""
                Take a function in the `\mathbf{w}` basis, and return its
                symmetric realization, when possible, expressed in the
                homogeneous basis of symmetric functions.

                OUTPUT:

                - If ``self`` is a symmetric function, then the expansion
                  in the homogeneous basis of the symmetric functions is returned.
                  Otherwise an error is raised.

                EXAMPLES::

                    sage: w = SymmetricFunctionsNonCommutingVariables(QQ).dual().w()
                    sage: elt = w[[1],[2,3]] + w[[1,2],[3]] + w[[1,3],[2]]
                    sage: elt.to_symmetric_function()
                    h[2, 1]
                    sage: elt = w.sum_of_partitions([2,1,1]) / 2
                    sage: elt.to_symmetric_function()
                    1/2*h[2, 1, 1]

                TESTS::

                    sage: w = SymmetricFunctionsNonCommutingVariables(QQ).dual().w()
                    sage: w(0).to_symmetric_function()
                    0
                    sage: w([]).to_symmetric_function()
                    h[]
                    sage: (2*w([])).to_symmetric_function()
                    2*h[]
                """
                if not self.is_symmetric():
                    raise ValueError("not a symmetric function")
                h = SymmetricFunctions(self.parent().base_ring()).homogeneous()
                d = {A.shape(): c for A, c in self}
                return h.sum_of_terms(
                    [(AA, cc / prod(map(factorial, AA.to_exp()))) for AA, cc in d.items()], distinct=True
                )

def _cl_term(n, R = RationalField()):
    r"""
    Compute the order-n term of the cycle index series of the virtual species `\Omega`,
    the compositional inverse of the species `E^{+}` of nonempty sets.

    EXAMPLES::

        sage: from sage.combinat.species.generating_series import _cl_term
        sage: [_cl_term(i) for i in range(4)]
        [0, p[1], -1/2*p[1, 1] - 1/2*p[2], 1/3*p[1, 1, 1] - 1/3*p[3]]
    """
    n = Integer(n)  # check that n is an integer

    p = SymmetricFunctions(R).power()

    res = p.zero()
    if n == 1:
        res = p([1])
    elif n > 1:
        res = 1/n * ((-1)**(n-1) * p([1])**n - sum(d * p([n // d]).plethysm(_cl_term(d, R)) for d in divisors(n)[:-1]))

    return res

        def cycle_index(self, parent = None):
            r"""
            INPUT:

             - ``self`` - a permutation group `G`
             - ``parent`` -- a free module with basis indexed by partitions,
               or behave as such, with a ``term`` and ``sum`` method
               (default: the symmetric functions over the rational field in the p basis)

            Returns the *cycle index* of `G`, which is a gadget counting
            the elements of `G` by cycle type, averaged over the group:

            .. math::

                P = \frac{1}{|G|} \sum_{g\in G} p_{ \operatorname{cycle\ type}(g) }

            EXAMPLES:

            Among the permutations of the symmetric group `S_4`, there is
            the identity, 6 cycles of length 2, 3 products of two cycles
            of length 2, 8 cycles of length 3, and 6 cycles of length 4::

                sage: S4 = SymmetricGroup(4)
                sage: P = S4.cycle_index()
                sage: 24 * P
                p[1, 1, 1, 1] + 6*p[2, 1, 1] + 3*p[2, 2] + 8*p[3, 1] + 6*p[4]

            If `l = (l_1,\dots,l_k)` is a partition, ``|G| P[l]`` is the number
            of elements of `G` with cycles of length `(p_1,\dots,p_k)`::

                sage: 24 * P[ Partition([3,1]) ]
                8

            The cycle index plays an important role in the enumeration of
            objects modulo the action of a group (Polya enumeration), via
            the use of symmetric functions and plethysms. It is therefore
            encoded as a symmetric function, expressed in the powersum
            basis::

                sage: P.parent()
                Symmetric Functions over Rational Field in the powersum basis

            This symmetric function can have some nice properties; for
            example, for the symmetric group `S_n`, we get the complete
            symmetric function `h_n`::

                sage: S = SymmetricFunctions(QQ); h = S.h()
                sage: h( P )
                h[4]

            TODO: add some simple examples of Polya enumeration, once it
            will be easy to expand symmetric functions on any alphabet.

            Here are the cycle indices of some permutation groups::

                sage: 6 * CyclicPermutationGroup(6).cycle_index()
                p[1, 1, 1, 1, 1, 1] + p[2, 2, 2] + 2*p[3, 3] + 2*p[6]

                sage: 60 * AlternatingGroup(5).cycle_index()
                p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]

                sage: for G in TransitiveGroups(5):               # optional - database_gap # long time
                ...       G.cardinality() * G.cycle_index()
                p[1, 1, 1, 1, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 10*p[4, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]
                p[1, 1, 1, 1, 1] + 10*p[2, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 20*p[3, 2] + 30*p[4, 1] + 24*p[5]

            One may specify another parent for the result::

                sage: F = CombinatorialFreeModule(QQ, Partitions())
                sage: P = CyclicPermutationGroup(6).cycle_index(parent = F)
                sage: 6 * P
                B[[1, 1, 1, 1, 1, 1]] + B[[2, 2, 2]] + 2*B[[3, 3]] + 2*B[[6]]
                sage: P.parent() is F
                True

            This parent should have a ``term`` and ``sum`` method::

                sage: CyclicPermutationGroup(6).cycle_index(parent = QQ)
                Traceback (most recent call last):
                  ...
                AssertionError: `parent` should be (or behave as) a free module with basis indexed by partitions

            REFERENCES:

             .. [Ker1991] A. Kerber. Algebraic combinatorics via finite group actions, 2.2 p. 70.
               BI-Wissenschaftsverlag, Mannheim, 1991.

            AUTHORS:

             - Nicolas Borie and Nicolas M. Thiery

            TESTS::

                sage: P = PermutationGroup([]); P
                Permutation Group with generators [()]
                sage: P.cycle_index()
                p[1]
#.........这里部分代码省略.........

def GL_irreducible_character(n, mu, KK):
    r"""
    Return the character of the irreducible module indexed by ``mu``
    of `GL(n)` over the field ``KK``.

    INPUT:

    - ``n`` -- a positive integer
    - ``mu`` -- a partition of at most ``n`` parts
    - ``KK`` -- a field

    OUTPUT:

    a symmetric function which should be interpreted in ``n``
    variables to be meaningful as a character

    EXAMPLES:

    Over `\QQ`, the irreducible character for `\mu` is the Schur
    function associated to `\mu`, plus garbage terms (Schur
    functions associated to partitions with more than `n` parts)::

        sage: from sage.algebras.schur_algebra import GL_irreducible_character
        sage: sbasis = SymmetricFunctions(QQ).s()
        sage: z = GL_irreducible_character(2, [2], QQ)
        sage: sbasis(z)
        s[2]

        sage: z = GL_irreducible_character(4, [3, 2], QQ)
        sage: sbasis(z)
        -5*s[1, 1, 1, 1, 1] + s[3, 2]

    Over a Galois field, the irreducible character for `\mu` will
    in general be smaller.

    In characteristic `p`, for a one-part partition `(r)`, where
    `r = a_0 + p a_1 + p^2 a_2 + \dots`, the result is (see [GreenPoly]_,
    after 5.5d) the product of `h[a_0], h[a_1]( pbasis[p]), h[a_2]
    ( pbasis[p^2]), \dots,` which is consistent with the following ::

        sage: from sage.algebras.schur_algebra import GL_irreducible_character
        sage: GL_irreducible_character(2, [7], GF(3))
        m[4, 3] + m[6, 1] + m[7]
    """
    mbasis = SymmetricFunctions(QQ).m()
    r = sum(mu)
    M = SchurTensorModule(KK, n, r)
    A = M._schur
    SGA = M._sga

    # make ST the superstandard tableau of shape mu
    from sage.combinat.tableau import from_shape_and_word

    ST = from_shape_and_word(mu, range(1, r + 1), convention="English")

    # make ell the reading word of the highest weight tableau of shape mu
    ell = [i + 1 for i, l in enumerate(mu) for dummy in range(l)]

    e = M.basis()[tuple(ell)]  # the element e_l

    # This is the notation `\{X\}` from just before (5.3a) of [GreenPoly]_.
    S = SGA._indices
    BracC = SGA._from_dict({S(x.tuple()): x.sign() for x in ST.column_stabilizer()}, remove_zeros=False)
    f = e * BracC  # M.action_by_symmetric_group_algebra(e, BracC)

    # [Green, Theorem 5.3b] says that a basis of the Carter-Lusztig
    # module V_\mu is given by taking this f, and multiplying by all
    # xi_{i,ell} with ell as above and i semistandard.

    carter_lusztig = []
    for T in SemistandardTableaux(mu, max_entry=n):
        i = tuple(flatten(T))
        schur_rep = schur_representative_from_index(i, tuple(ell))
        y = A.basis()[schur_rep] * e  # M.action_by_Schur_alg(A.basis()[schur_rep], e)
        carter_lusztig.append(y.to_vector())

    # Therefore, we now have carter_lusztig as a list giving the basis
    # of `V_\mu`

    # We want to think of expressing this character as a sum of monomial
    # symmetric functions.

    # We will determine a basis element for each m_\lambda in the
    # character, and we want to keep track of them by \lambda.

    # That means that we only want to pick out the basis elements above for
    # those semistandard words whose content is a partition.

    contents = Partitions(r, max_length=n).list()
    # all partitions of r, length at most n

    # JJ will consist of a list for each element of `contents`,
    # recording the list
    # of semistandard tableaux words with that content

    # graded_basis will consist of the a corresponding basis element
    graded_basis = []
    JJ = []
    for i in range(len(contents)):
        graded_basis.append([])
#.........这里部分代码省略.........

        def cycle_index(self, parent = None):
            r"""
            Return the *cycle index* of ``self``.

            INPUT:

             - ``self`` - a permutation group `G`
             - ``parent`` -- a free module with basis indexed by partitions,
               or behave as such, with a ``term`` and ``sum`` method
               (default: the symmetric functions over the rational field in the `p` basis)

            The *cycle index* of a permutation group `G`
            (:wikipedia:`Cycle_index`) is a gadget counting the
            elements of `G` by cycle type, averaged over the group:

            .. MATH::

                P = \frac{1}{|G|} \sum_{g\in G} p_{ \operatorname{cycle\ type}(g) }

            EXAMPLES:

            Among the permutations of the symmetric group `S_4`, there is
            the identity, 6 cycles of length 2, 3 products of two cycles
            of length 2, 8 cycles of length 3, and 6 cycles of length 4::

                sage: S4 = SymmetricGroup(4)
                sage: P = S4.cycle_index()
                sage: 24 * P
                p[1, 1, 1, 1] + 6*p[2, 1, 1] + 3*p[2, 2] + 8*p[3, 1] + 6*p[4]

            If `l = (l_1,\dots,l_k)` is a partition, ``|G| P[l]`` is the number
            of elements of `G` with cycles of length `(p_1,\dots,p_k)`::

                sage: 24 * P[ Partition([3,1]) ]
                8

            The cycle index plays an important role in the enumeration of
            objects modulo the action of a group (Pólya enumeration), via
            the use of symmetric functions and plethysms. It is therefore
            encoded as a symmetric function, expressed in the powersum
            basis::

                sage: P.parent()
                Symmetric Functions over Rational Field in the powersum basis

            This symmetric function can have some nice properties; for
            example, for the symmetric group `S_n`, we get the complete
            symmetric function `h_n`::

                sage: S = SymmetricFunctions(QQ); h = S.h()
                sage: h( P )
                h[4]

            .. TODO::

                Add some simple examples of Pólya enumeration, once
                it will be easy to expand symmetric functions on any
                alphabet.

            Here are the cycle indices of some permutation groups::

                sage: 6 * CyclicPermutationGroup(6).cycle_index()
                p[1, 1, 1, 1, 1, 1] + p[2, 2, 2] + 2*p[3, 3] + 2*p[6]

                sage: 60 * AlternatingGroup(5).cycle_index()
                p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]

                sage: for G in TransitiveGroups(5):               # optional - database_gap # long time
                ....:     G.cardinality() * G.cycle_index()
                p[1, 1, 1, 1, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 10*p[4, 1] + 4*p[5]
                p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]
                p[1, 1, 1, 1, 1] + 10*p[2, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 20*p[3, 2] + 30*p[4, 1] + 24*p[5]

            Permutation groups with arbitrary domains are supported
            (see :trac:`22765`)::

                sage: G = PermutationGroup([['b','c','a']], domain=['a','b','c'])
                sage: G.cycle_index()
                1/3*p[1, 1, 1] + 2/3*p[3]

            One may specify another parent for the result::

                sage: F = CombinatorialFreeModule(QQ, Partitions())
                sage: P = CyclicPermutationGroup(6).cycle_index(parent = F)
                sage: 6 * P
                B[[1, 1, 1, 1, 1, 1]] + B[[2, 2, 2]] + 2*B[[3, 3]] + 2*B[[6]]
                sage: P.parent() is F
                True

            This parent should be a module with basis indexed by partitions::

                sage: CyclicPermutationGroup(6).cycle_index(parent = QQ)
                Traceback (most recent call last):
                  ...
                ValueError: `parent` should be a module with basis indexed by partitions

            REFERENCES:

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