Coverage for local/lib/python2.7/site-packages/sage/combinat/ncsym/ncsym.py : 74%

""" 

Symmetric Functions in Non-Commuting Variables 

AUTHORS: 

- Travis Scrimshaw (08-04-2013): Initial version 

""" 

#***************************************************************************** 

# Copyright (C) 2013 Travis Scrimshaw <tscrim at ucdavis.edu> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from six.moves import range 

from sage.misc.cachefunc import cached_method 

#from sage.misc.lazy_attribute import lazy_attribute 

from sage.misc.misc_c import prod 

from sage.structure.parent import Parent 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.categories.graded_hopf_algebras import GradedHopfAlgebras 

from sage.categories.rings import Rings 

from sage.categories.fields import Fields 

from sage.functions.other import factorial 

from sage.combinat.free_module import CombinatorialFreeModule 

from sage.combinat.ncsym.bases import NCSymBases, MultiplicativeNCSymBases, NCSymBasis_abstract 

from sage.combinat.set_partition import SetPartitions 

from sage.combinat.set_partition_ordered import OrderedSetPartitions 

from sage.combinat.posets.posets import Poset 

from sage.combinat.sf.sf import SymmetricFunctions 

from sage.matrix.matrix_space import MatrixSpace 

from sage.sets.set import Set 

from sage.rings.all import ZZ 

from functools import reduce 

def matchings(A, B): 

""" 

Iterate through all matchings of the sets `A` and `B`. 

EXAMPLES:: 

sage: from sage.combinat.ncsym.ncsym import matchings 

sage: list(matchings([1, 2, 3], [-1, -2])) 

[[[1], [2], [3], [-1], [-2]], 

[[1], [2], [3, -1], [-2]], 

[[1], [2], [3, -2], [-1]], 

[[1], [2, -1], [3], [-2]], 

[[1], [2, -1], [3, -2]], 

[[1], [2, -2], [3], [-1]], 

[[1], [2, -2], [3, -1]], 

[[1, -1], [2], [3], [-2]], 

[[1, -1], [2], [3, -2]], 

[[1, -1], [2, -2], [3]], 

[[1, -2], [2], [3], [-1]], 

[[1, -2], [2], [3, -1]], 

[[1, -2], [2, -1], [3]]] 

""" 

lst_A = list(A) 

lst_B = list(B) 

# Handle corner cases 

if not lst_A: 

if not lst_B: 

yield [] 

else: 

yield [[b] for b in lst_B] 

return 

if not lst_B: 

yield [[a] for a in lst_A] 

return 

rem_A = lst_A[:] 

a = rem_A.pop(0) 

for m in matchings(rem_A, lst_B): 

yield [[a]] + m 

for i in range(len(lst_B)): 

rem_B = lst_B[:] 

b = rem_B.pop(i) 

for m in matchings(rem_A, rem_B): 

yield [[a, b]] + m 

def nesting(la, nu): 

r""" 

Return the nesting number of ``la`` inside of ``nu``. 

If we consider a set partition `A` as a set of arcs `i - j` where `i` 

and `j` are in the same part of `A`. Define 

.. MATH:: 

\operatorname{nst}_{\lambda}^{\nu} = \#\{ i < j < k < l \mid 

i - l \in \nu, j - k \in \lambda \}, 

and this corresponds to the number of arcs of `\lambda` strictly 

contained inside of `\nu`. 

EXAMPLES:: 

sage: from sage.combinat.ncsym.ncsym import nesting 

sage: nu = SetPartition([[1,4], [2], [3]]) 

sage: mu = SetPartition([[1,4], [2,3]]) 

sage: nesting(set(mu).difference(nu), nu) 

1 

:: 

sage: lst = list(SetPartitions(4)) 

sage: d = {} 

sage: for i, nu in enumerate(lst): 

....: for mu in nu.coarsenings(): 

....: if set(nu.arcs()).issubset(mu.arcs()): 

....: d[i, lst.index(mu)] = nesting(set(mu).difference(nu), nu) 

sage: matrix(d) 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 1 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 

""" 

arcs = [] 

for p in nu: 

p = sorted(p) 

arcs += [(p[i], p[i+1]) for i in range(len(p)-1)] 

nst = 0 

for p in la: 

p = sorted(p) 

for i in range(len(p)-1): 

for a in arcs: 

if a[0] >= p[i]: 

break 

if p[i+1] < a[1]: 

nst += 1 

return nst 

class SymmetricFunctionsNonCommutingVariables(UniqueRepresentation, Parent): 

r""" 

Symmetric functions in non-commutative variables. 

The ring of symmetric functions in non-commutative variables, 

which is not to be confused with the :class:`non-commutative symmetric 

functions<NonCommutativeSymmetricFunctions>`, is the ring of all 

bounded-degree noncommutative power series in countably many 

indeterminates (i.e., elements in 

`R \langle \langle x_1, x_2, x_3, \ldots \rangle \rangle` of bounded 

degree) which are invariant with respect to the action of the 

symmetric group `S_{\infty}` on the indices of the indeterminates. 

It can be regarded as a direct limit over all `n \to \infty` of rings 

of `S_n`-invariant polynomials in `n` non-commuting variables 

(that is, `S_n`-invariant elements of `R\langle x_1, x_2, \ldots, x_n \rangle`). 

This ring is implemented as a Hopf algebra whose basis elements are 

indexed by set partitions. 

Let `A = \{A_1, A_2, \ldots, A_r\}` be a set partition of the integers 

`\{ 1, 2, \ldots, k \}`. A monomial basis element indexed by `A` 

represents the sum of monomials `x_{i_1} x_{i_2} \cdots x_{i_k}` where 

`i_c = i_d` if and only if `c` and `d` are in the same part `A_i` for some `i`. 

The `k`-th graded component of the ring of symmetric functions in 

non-commutative variables has its dimension equal to the number of 

set partitions of `k`. (If we work, instead, with finitely many -- 

say, `n` -- variables, then its dimension is equal to the number of 

set partitions of `k` where the number of parts is at most `n`.) 

.. NOTE:: 

All set partitions are considered standard, a set partition of `[n]` 

for some `n`, unless otherwise stated. 

REFERENCES: 

.. [BZ05] \N. Bergeron, M. Zabrocki. *The Hopf algebra of symmetric 

functions and quasisymmetric functions in non-commutative variables 

are free and cofree*. (2005). :arxiv:`math/0509265v3`. 

.. [BHRZ06] \N. Bergeron, C. Hohlweg, M. Rosas, M. Zabrocki. 

*Grothendieck bialgebras, partition lattices, and symmetric 

functions in noncommutative variables*. Electronic Journal of 

Combinatorics. **13** (2006). 

.. [RS06] \M. Rosas, B. Sagan. *Symmetric functions in noncommuting 

variables*. Trans. Amer. Math. Soc. **358** (2006). no. 1, 215-232. 

:arxiv:`math/0208168`. 

.. [BRRZ08] \N. Bergeron, C. Reutenauer, M. Rosas, M. Zabrocki. 

*Invariants and coinvariants of the symmetric group in noncommuting 

variables*. Canad. J. Math. **60** (2008). 266-296. 

:arxiv:`math/0502082` 

.. [BT13] \N. Bergeron, N. Thiem. *A supercharacter table decomposition 

via power-sum symmetric functions*. Int. J. Algebra Comput. **23**, 

763 (2013). :doi:`10.1142/S0218196713400171`. :arxiv:`1112.4901`. 

EXAMPLES: 

We begin by first creating the ring of `NCSym` and the bases that are 

analogues of the usual symmetric functions:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: m = NCSym.m() 

sage: e = NCSym.e() 

sage: h = NCSym.h() 

sage: p = NCSym.p() 

sage: m 

Symmetric functions in non-commuting variables over the Rational Field in the monomial basis 

The basis is indexed by set partitions, so we create a few elements and 

convert them between these bases:: 

sage: elt = m(SetPartition([[1,3],[2]])) - 2*m(SetPartition([[1],[2]])); elt 

-2*m{{1}, {2}} + m{{1, 3}, {2}} 

sage: e(elt) 

1/2*e{{1}, {2, 3}} - 2*e{{1, 2}} + 1/2*e{{1, 2}, {3}} - 1/2*e{{1, 2, 3}} - 1/2*e{{1, 3}, {2}} 

sage: h(elt) 

-4*h{{1}, {2}} - 2*h{{1}, {2}, {3}} + 1/2*h{{1}, {2, 3}} + 2*h{{1, 2}} 

+ 1/2*h{{1, 2}, {3}} - 1/2*h{{1, 2, 3}} + 3/2*h{{1, 3}, {2}} 

sage: p(elt) 

-2*p{{1}, {2}} + 2*p{{1, 2}} - p{{1, 2, 3}} + p{{1, 3}, {2}} 

sage: m(p(elt)) 

-2*m{{1}, {2}} + m{{1, 3}, {2}} 

sage: elt = p(SetPartition([[1,3],[2]])) - 4*p(SetPartition([[1],[2]])) + 2; elt 

2*p{} - 4*p{{1}, {2}} + p{{1, 3}, {2}} 

sage: e(elt) 

2*e{} - 4*e{{1}, {2}} + e{{1}, {2}, {3}} - e{{1, 3}, {2}} 

sage: m(elt) 

2*m{} - 4*m{{1}, {2}} - 4*m{{1, 2}} + m{{1, 2, 3}} + m{{1, 3}, {2}} 

sage: h(elt) 

2*h{} - 4*h{{1}, {2}} - h{{1}, {2}, {3}} + h{{1, 3}, {2}} 

sage: p(m(elt)) 

2*p{} - 4*p{{1}, {2}} + p{{1, 3}, {2}} 

There is also a shorthand for creating elements. We note that we must use 

``p[[]]`` to create the empty set partition due to python's syntax. :: 

sage: eltm = m[[1,3],[2]] - 3*m[[1],[2]]; eltm 

-3*m{{1}, {2}} + m{{1, 3}, {2}} 

sage: elte = e[[1,3],[2]]; elte 

e{{1, 3}, {2}} 

sage: elth = h[[1,3],[2,4]]; elth 

h{{1, 3}, {2, 4}} 

sage: eltp = p[[1,3],[2,4]] + 2*p[[1]] - 4*p[[]]; eltp 

-4*p{} + 2*p{{1}} + p{{1, 3}, {2, 4}} 

There is also a natural projection to the usual symmetric functions by 

letting the variables commute. This projection map preserves the product 

and coproduct structure. We check that Theorem 2.1 of [RS06]_ holds:: 

sage: Sym = SymmetricFunctions(QQ) 

sage: Sm = Sym.m() 

sage: Se = Sym.e() 

sage: Sh = Sym.h() 

sage: Sp = Sym.p() 

sage: eltm.to_symmetric_function() 

-6*m[1, 1] + m[2, 1] 

sage: Sm(p(eltm).to_symmetric_function()) 

-6*m[1, 1] + m[2, 1] 

sage: elte.to_symmetric_function() 

2*e[2, 1] 

sage: Se(h(elte).to_symmetric_function()) 

2*e[2, 1] 

sage: elth.to_symmetric_function() 

4*h[2, 2] 

sage: Sh(m(elth).to_symmetric_function()) 

4*h[2, 2] 

sage: eltp.to_symmetric_function() 

-4*p[] + 2*p[1] + p[2, 2] 

sage: Sp(e(eltp).to_symmetric_function()) 

-4*p[] + 2*p[1] + p[2, 2] 

""" 

def __init__(self, R): 

""" 

Initialize ``self``. 

EXAMPLES:: 

sage: NCSym1 = SymmetricFunctionsNonCommutingVariables(FiniteField(23)) 

sage: NCSym2 = SymmetricFunctionsNonCommutingVariables(Integers(23)) 

sage: TestSuite(SymmetricFunctionsNonCommutingVariables(QQ)).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()) 

def _repr_(self): 

r""" 

EXAMPLES:: 

sage: SymmetricFunctionsNonCommutingVariables(ZZ) 

Symmetric functions in non-commuting variables over the Integer Ring 

""" 

return "Symmetric functions in non-commuting variables over the %s"%self.base_ring() 

def a_realization(self): 

r""" 

Return the realization of the powersum basis of ``self``. 

OUTPUT: 

- The powersum basis of symmetric functions in non-commuting variables. 

EXAMPLES:: 

sage: SymmetricFunctionsNonCommutingVariables(QQ).a_realization() 

Symmetric functions in non-commuting variables over the Rational Field in the powersum basis 

""" 

return self.powersum() 

_shorthands = tuple(['chi', 'cp', 'm', 'e', 'h', 'p', 'rho', 'x']) 

def dual(self): 

r""" 

Return the dual Hopf algebra of the symmetric functions in 

non-commuting variables. 

EXAMPLES:: 

sage: SymmetricFunctionsNonCommutingVariables(QQ).dual() 

Dual symmetric functions in non-commuting variables over the Rational Field 

""" 

from sage.combinat.ncsym.dual import SymmetricFunctionsNonCommutingVariablesDual 

return SymmetricFunctionsNonCommutingVariablesDual(self.base_ring()) 

class monomial(NCSymBasis_abstract): 

r""" 

The Hopf algebra of symmetric functions in non-commuting variables 

in the monomial basis. 

EXAMPLES:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: m = NCSym.m() 

sage: m[[1,3],[2]]*m[[1,2]] 

m{{1, 3}, {2}, {4, 5}} + m{{1, 3}, {2, 4, 5}} + m{{1, 3, 4, 5}, {2}} 

sage: m[[1,3],[2]].coproduct() 

m{} # m{{1, 3}, {2}} + m{{1}} # m{{1, 2}} + m{{1, 2}} # m{{1}} + m{{1, 

3}, {2}} # m{} 

""" 

def __init__(self, NCSym): 

""" 

EXAMPLES:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: TestSuite(NCSym.m()).run() 

""" 

CombinatorialFreeModule.__init__(self, NCSym.base_ring(), SetPartitions(), 

prefix='m', bracket=False, 

category=NCSymBases(NCSym)) 

@cached_method 

def _m_to_p_on_basis(self, A): 

r""" 

Return `\mathbf{m}_A` in terms of the powersum basis. 

INPUT: 

- ``A`` -- a set partition 

OUTPUT: 

- An element of the powersum basis 

TESTS:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: m = NCSym.m() 

sage: all(m(m._m_to_p_on_basis(A)) == m[A] for i in range(5) 

....: for A in SetPartitions(i)) 

True 

""" 

def lt(s, t): 

if s == t: 

return False 

for p in s: 

if len([ z for z in list(t) if z.intersection(p) != Set([]) ]) != 1: 

return False 

return True 

p = self.realization_of().p() 

P = Poset((A.coarsenings(), lt)) 

R = self.base_ring() 

return p._from_dict({B: R(P.moebius_function(A, B)) for B in P}) 

@cached_method 

def _m_to_cp_on_basis(self, A): 

r""" 

Return `\mathbf{m}_A` in terms of the `\mathbf{cp}` basis. 

INPUT: 

- ``A`` -- a set partition 

OUTPUT: 

- An element of the `\mathbf{cp}` basis 

TESTS:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: m = NCSym.m() 

sage: all(m(m._m_to_cp_on_basis(A)) == m[A] for i in range(5) 

....: for A in SetPartitions(i)) 

True 

""" 

cp = self.realization_of().cp() 

arcs = set(A.arcs()) 

R = self.base_ring() 

return cp._from_dict({B: R((-1)**len(set(B.arcs()).difference(A.arcs()))) 

for B in A.coarsenings() if arcs.issubset(B.arcs())}, 

remove_zeros=False) 

def from_symmetric_function(self, f): 

""" 

Return the image of the symmetric function ``f`` in ``self``. 

This is performed by converting to the monomial basis and 

extending the method :meth:`sum_of_partitions` linearly. This is a 

linear map from the symmetric functions to the symmetric functions 

in non-commuting variables that does not preserve the product or 

coproduct structure of the Hopf algebra. 

.. SEEALSO:: :meth:`~Element.to_symmetric_function` 

INPUT: 

- ``f`` -- an element of the symmetric functions 

OUTPUT: 

- An element of the `\mathbf{m}` basis 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).m() 

sage: mon = SymmetricFunctions(QQ).m() 

sage: elt = m.from_symmetric_function(mon[2,1,1]); elt 

1/12*m{{1}, {2}, {3, 4}} + 1/12*m{{1}, {2, 3}, {4}} + 1/12*m{{1}, {2, 4}, {3}} 

+ 1/12*m{{1, 2}, {3}, {4}} + 1/12*m{{1, 3}, {2}, {4}} + 1/12*m{{1, 4}, {2}, {3}} 

sage: elt.to_symmetric_function() 

m[2, 1, 1] 

sage: e = SymmetricFunctionsNonCommutingVariables(QQ).e() 

sage: elm = SymmetricFunctions(QQ).e() 

sage: e(m.from_symmetric_function(elm[4])) 

1/24*e{{1, 2, 3, 4}} 

sage: h = SymmetricFunctionsNonCommutingVariables(QQ).h() 

sage: hom = SymmetricFunctions(QQ).h() 

sage: h(m.from_symmetric_function(hom[4])) 

1/24*h{{1, 2, 3, 4}} 

sage: p = SymmetricFunctionsNonCommutingVariables(QQ).p() 

sage: pow = SymmetricFunctions(QQ).p() 

sage: p(m.from_symmetric_function(pow[4])) 

p{{1, 2, 3, 4}} 

sage: p(m.from_symmetric_function(pow[2,1])) 

1/3*p{{1}, {2, 3}} + 1/3*p{{1, 2}, {3}} + 1/3*p{{1, 3}, {2}} 

sage: p([[1,2]])*p([[1]]) 

p{{1, 2}, {3}} 

Check that `\chi \circ \widetilde{\chi}` is the identity on `Sym`:: 

sage: all(m.from_symmetric_function(pow(la)).to_symmetric_function() == pow(la) 

....: for la in Partitions(4)) 

True 

""" 

m = SymmetricFunctions(self.base_ring()).m() 

return self.sum([c * self.sum_of_partitions(i) for i,c in m(f)]) 

def dual_basis(self): 

r""" 

Return the dual basis to the monomial basis. 

OUTPUT: 

- the `\mathbf{w}` basis of the dual Hopf algebra 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).m() 

sage: m.dual_basis() 

Dual symmetric functions in non-commuting variables over the Rational Field in the w basis 

""" 

return self.realization_of().dual().w() 

def duality_pairing(self, x, y): 

r""" 

Compute the pairing between an element of ``self`` and an element 

of the dual. 

INPUT: 

- ``x`` -- an element of symmetric functions in non-commuting 

variables 

- ``y`` -- an element of the dual of symmetric functions in 

non-commuting variables 

OUTPUT: 

- an element of the base ring of ``self`` 

EXAMPLES:: 

sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) 

sage: m = NCSym.m() 

sage: w = m.dual_basis() 

sage: matrix([[m(A).duality_pairing(w(B)) for A in SetPartitions(3)] for B in SetPartitions(3)]) 

[1 0 0 0 0] 

[0 1 0 0 0] 

[0 0 1 0 0] 

[0 0 0 1 0] 

[0 0 0 0 1] 

sage: (m[[1,2],[3]] + 3*m[[1,3],[2]]).duality_pairing(2*w[[1,3],[2]] + w[[1,2,3]] + 2*w[[1,2],[3]]) 

8 

""" 

x = self(x) 

y = self.dual_basis()(y) 

return sum(coeff * y[I] for (I, coeff) in x) 

def product_on_basis(self, A, B): 

r""" 

The product on monomial basis elements. 

The product of the basis elements indexed by two set partitions `A` 

and `B` is the sum of the basis elements indexed by set partitions 

`C` such that `C \wedge ([n] | [k]) = A | B` where `n = |A|` 

and `k = |B|`. Here `A \wedge B` is the infimum of `A` and `B` 

and `A | B` is the 

:meth:`SetPartition.pipe` operation. 

Equivalently we can describe all `C` as matchings between the 

partitions of `A` and `B` where if `a \in A` is matched 

with `b \in B`, we take `a \cup b` instead of `a` and `b` in `C`. 

INPUT: 

- ``A``, ``B`` -- set partitions 

OUTPUT: 

- an element of the `\mathbf{m}` basis 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).monomial() 

sage: A = SetPartition([[1], [2,3]]) 

sage: B = SetPartition([[1], [3], [2,4]]) 

sage: m.product_on_basis(A, B) 

m{{1}, {2, 3}, {4}, {5, 7}, {6}} + m{{1}, {2, 3, 4}, {5, 7}, {6}} 

+ m{{1}, {2, 3, 5, 7}, {4}, {6}} + m{{1}, {2, 3, 6}, {4}, {5, 7}} 

+ m{{1, 4}, {2, 3}, {5, 7}, {6}} + m{{1, 4}, {2, 3, 5, 7}, {6}} 

+ m{{1, 4}, {2, 3, 6}, {5, 7}} + m{{1, 5, 7}, {2, 3}, {4}, {6}} 

+ m{{1, 5, 7}, {2, 3, 4}, {6}} + m{{1, 5, 7}, {2, 3, 6}, {4}} 

+ m{{1, 6}, {2, 3}, {4}, {5, 7}} + m{{1, 6}, {2, 3, 4}, {5, 7}} 

+ m{{1, 6}, {2, 3, 5, 7}, {4}} 

sage: B = SetPartition([[1], [2]]) 

sage: m.product_on_basis(A, B) 

m{{1}, {2, 3}, {4}, {5}} + m{{1}, {2, 3, 4}, {5}} 

+ m{{1}, {2, 3, 5}, {4}} + m{{1, 4}, {2, 3}, {5}} + m{{1, 4}, {2, 3, 5}} 

+ m{{1, 5}, {2, 3}, {4}} + m{{1, 5}, {2, 3, 4}} 

sage: m.product_on_basis(A, SetPartition([])) 

m{{1}, {2, 3}} 

TESTS: 

We check that we get all of the correct set partitions:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).monomial() 

sage: A = SetPartition([[1], [2,3]]) 

sage: B = SetPartition([[1], [2]]) 

sage: S = SetPartition([[1,2,3], [4,5]]) 

sage: AB = SetPartition([[1], [2,3], [4], [5]]) 

sage: L = sorted(filter(lambda x: S.inf(x) == AB, SetPartitions(5)), key=str) 

sage: list(map(list, L)) == list(map(list, sorted(m.product_on_basis(A, B).support(), key=str))) 

True 

""" 

if not A: 

return self.monomial(B) 

if not B: 

return self.monomial(A) 

P = SetPartitions() 

n = A.size() 

B = [Set([y+n for y in b]) for b in B] # Shift B by n 

unions = lambda m: [reduce(lambda a,b: a.union(b), x) for x in m] 

one = self.base_ring().one() 

return self._from_dict({P(unions(m)): one for m in matchings(A, B)}, 

remove_zeros=False) 

def coproduct_on_basis(self, A): 

r""" 

Return the coproduct of a monomial basis element. 

INPUT: 

- ``A`` -- a set partition 

OUTPUT: 

- The coproduct applied to the monomial symmetric function in 

non-commuting variables indexed by ``A`` expressed in the 

monomial basis. 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).monomial() 

sage: m[[1, 3], [2]].coproduct() 

m{} # m{{1, 3}, {2}} + m{{1}} # m{{1, 2}} + m{{1, 2}} # m{{1}} + m{{1, 3}, {2}} # m{} 

sage: m.coproduct_on_basis(SetPartition([])) 

m{} # m{} 

sage: m.coproduct_on_basis(SetPartition([[1,2,3]])) 

m{} # m{{1, 2, 3}} + m{{1, 2, 3}} # m{} 

sage: m[[1,5],[2,4],[3,7],[6]].coproduct() 

m{} # m{{1, 5}, {2, 4}, {3, 7}, {6}} + m{{1}} # m{{1, 5}, {2, 4}, {3, 6}} 

+ 2*m{{1, 2}} # m{{1, 3}, {2, 5}, {4}} + m{{1, 2}} # m{{1, 4}, {2, 3}, {5}} 

+ 2*m{{1, 2}, {3}} # m{{1, 3}, {2, 4}} + m{{1, 3}, {2}} # m{{1, 4}, {2, 3}} 

+ 2*m{{1, 3}, {2, 4}} # m{{1, 2}, {3}} + 2*m{{1, 3}, {2, 5}, {4}} # m{{1, 2}} 

+ m{{1, 4}, {2, 3}} # m{{1, 3}, {2}} + m{{1, 4}, {2, 3}, {5}} # m{{1, 2}} 

+ m{{1, 5}, {2, 4}, {3, 6}} # m{{1}} + m{{1, 5}, {2, 4}, {3, 7}, {6}} # m{} 

""" 

P = SetPartitions() 

# Handle corner cases 

if not A: 

return self.tensor_square().monomial(( P([]), P([]) )) 

if len(A) == 1: 

return self.tensor_square().sum_of_monomials([(P([]), A), (A, P([]))]) 

ell_set = list(range(1, len(A) + 1)) # +1 for indexing 

L = [[[], ell_set]] + list(SetPartitions(ell_set, 2)) 

def to_basis(S): 

if not S: 

return P([]) 

sub_parts = [list(A[i-1]) for i in S] # -1 for indexing 

mins = [min(p) for p in sub_parts] 

over_max = max([max(p) for p in sub_parts]) + 1 

ret = [[] for i in range(len(S))] 

cur = 1 

while min(mins) != over_max: 

m = min(mins) 

i = mins.index(m) 

ret[i].append(cur) 

cur += 1 

sub_parts[i].pop(sub_parts[i].index(m)) 

if sub_parts[i]: 

mins[i] = min(sub_parts[i]) 

else: 

mins[i] = over_max 

return P(ret) 

L1 = [(to_basis(S), to_basis(C)) for S,C in L] 

L2 = [(M, N) for N,M in L1] 

return self.tensor_square().sum_of_monomials(L1 + L2) 

def internal_coproduct_on_basis(self, A): 

r""" 

Return the internal coproduct of a monomial basis element. 

The internal coproduct is defined by 

.. MATH:: 

\Delta^{\odot}(\mathbf{m}_A) = \sum_{B \wedge C = A} 

\mathbf{m}_B \otimes \mathbf{m}_C 

where we sum over all pairs of set partitions `B` and `C` 

whose infimum is `A`. 

INPUT: 

- ``A`` -- a set partition 

OUTPUT: 

- an element of the tensor square of the `\mathbf{m}` basis 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).monomial() 

sage: m.internal_coproduct_on_basis(SetPartition([[1,3],[2]])) 

m{{1, 2, 3}} # m{{1, 3}, {2}} + m{{1, 3}, {2}} # m{{1, 2, 3}} + m{{1, 3}, {2}} # m{{1, 3}, {2}} 

""" 

P = SetPartitions() 

SP = SetPartitions(A.size()) 

ret = [[A,A]] 

for i, B in enumerate(SP): 

for C in SP[i+1:]: 

if B.inf(C) == A: 

B_std = P(list(B.standardization())) 

C_std = P(list(C.standardization())) 

ret.append([B_std, C_std]) 

ret.append([C_std, B_std]) 

return self.tensor_square().sum_of_monomials((B, C) for B,C in ret) 

def sum_of_partitions(self, la): 

r""" 

Return the sum over all set partitions whose shape is ``la`` 

with a fixed coefficient `C` defined below. 

Fix a partition `\lambda`, we define 

`\lambda! := \prod_i \lambda_i!` and `\lambda^! := \prod_i m_i!`. 

Recall that `|\lambda| = \sum_i \lambda_i` and `m_i` is the 

number of parts of length `i` of `\lambda`. Thus we defined the 

coefficient as 

.. MATH:: 

C := \frac{\lambda! \lambda^!}{|\lambda|!}. 

Hence we can define a lift `\widetilde{\chi}` from `Sym` 

to `NCSym` by 

.. MATH:: 

m_{\lambda} \mapsto C \sum_A \mathbf{m}_A 

where the sum is over all set partitions whose shape 

is `\lambda`. 

INPUT: 

- ``la`` -- an integer partition 

OUTPUT: 

- an element of the `\mathbf{m}` basis 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).m() 

sage: m.sum_of_partitions(Partition([2,1,1])) 

1/12*m{{1}, {2}, {3, 4}} + 1/12*m{{1}, {2, 3}, {4}} + 1/12*m{{1}, {2, 4}, {3}} 

+ 1/12*m{{1, 2}, {3}, {4}} + 1/12*m{{1, 3}, {2}, {4}} + 1/12*m{{1, 4}, {2}, {3}} 

TESTS: 

Check that `\chi \circ \widetilde{\chi}` is the identity on `Sym`:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).m() 

sage: mon = SymmetricFunctions(QQ).monomial() 

sage: all(m.from_symmetric_function(mon[la]).to_symmetric_function() == mon[la] 

....: for i in range(6) for la in Partitions(i)) 

True 

""" 

from sage.combinat.partition import Partition 

la = Partition(la) # Make sure it is a partition 

R = self.base_ring() 

P = SetPartitions() 

c = R( prod(factorial(i) for i in la) / ZZ(factorial(la.size())) ) 

return self._from_dict({P(m): c for m in SetPartitions(sum(la), la)}, 

remove_zeros=False) 

class Element(CombinatorialFreeModule.Element): 

""" 

An element in the monomial basis of `NCSym`. 

""" 

def expand(self, n, alphabet='x'): 

r""" 

Expand ``self`` written in the monomial basis in `n` 

non-commuting variables. 

INPUT: 

- ``n`` -- an integer 

- ``alphabet`` -- (default: ``'x'``) a string 

OUTPUT: 

- The symmetric function of ``self`` expressed in the ``n`` 

non-commuting variables described by ``alphabet``. 

EXAMPLES:: 

sage: m = SymmetricFunctionsNonCommutingVariables(QQ).monomial() 

sage: m[[1,3],[2]].expand(4) 

x0*x1*x0 + x0*x2*x0 + x0*x3*x0 + x1*x0*x1 + x1*x2*x1 + x1*x3*x1 

+ x2*x0*x2 + x2*x1*x2 + x2*x3*x2 + x3*x0*x3 + x3*x1*x3 + x3*x2*x3 

One can use a different set of variables by using the 

optional argument ``alphabet``:: 

sage: m[[1],[2,3]].expand(3,alphabet='y') 

y0*y1^2 + y0*y2^2 + y1*y0^2 + y1*y2^2 + y2*y0^2 + y2*y1^2 

""" 

from sage.algebras.free_algebra import FreeAlgebra 

from sage.combinat.permutation import Permutations 

m = self.parent() 

F = FreeAlgebra(m.base_ring(), n, alphabet)