>> export(operators, coproduct):
operators::setTensorSymbol("#"):
lra := examples::LodayRoncoAlgebra():
>> tree := combinat::binaryTrees([NIL, [NIL], [NIL]])
>> 2*tree + 1
>> tree*tree
>> (1+tree) * tree
>> tree * (1+tree)
>> el := lra::p(tree)
>> 2*el + 1
>> el*el
>> eh1 := lra::h(combinat::binaryTrees([NIL, [NIL, [NIL]]]))
>> eh2 := lra::h(combinat::binaryTrees([NIL, [NIL, [NIL], [NIL]]]))
>> eh1*eh2
>> eh2*eh1
>> el
>> elh := lra::h(el)
>> lra::p(elh^2)
>> el^2
>> tens := coproduct(el)
>> idTensorAntipode := lra::p::id # lra::p::antipode:
>> idTensorAntipode(tens)
>> checkAntipode := lra::p::mu @ idTensorAntipode @ lra::p::coproduct:
>> t := lra::p::one;
checkAntipode(t)
>> t := lra::p::basis::random(5);
checkAntipode(t)
>> read("experimental/2007-09-11-kshapeweights.mu"):
view(8,3)
>> export(combinat):
Many standard combinatorial classes are predefined in MuPAD-Combinat. Each is represented by a library with a standardized interface:
>> trees::list(5)
>> trees::count(5)
>> trees::random(50)
A typical standard skew tableaux:
>> skewTableaux([[3, 1],
[[5],
[3, 6, 8],
[1, 2, 9],
[4, 7]]])
There are quite a few standard skew tableaux of this shape:
>> skewTableaux::count([[5, 4, 3, 1], [3, 1]])
So, we use a generator to get them one by one:
>> g := skewTableaux::generator([[5, 4, 3, 1], [3, 1]]):
>> g()
>> g()
>> g()
>> g()
>> domain oddIntegers
// This is a domain (not a library):
inherits Dom::BaseDomain;
// This is a graded combinatorial class:
category Cat::GradedCombinatorialClass,
// and a facade domain:
Cat::FacadeDomain(DOM_INT);
info_str := "The class of non negative odd integers";
isA := n -> bool(testtype(n, Type::PosInt) and
n mod 2 <> 0);
// The size of an odd integer is itself
size := n -> n;
count := n -> if n mod 2 = 1 then 1 else 0 end_if;
list := n -> if n mod 2 = 1 then [n] else [] end_if;
// No need to define generator;
// it is defined via list by default
end_domain:
What's the point?
It can be used as building block for constructing new combinatorial classes like, say, integer partitions with odd parts:
>> oddPartsPartitions := combinat::decomposableObjects
([Part = Multiset(oddIntegers)]):
>> oddPartsPartitions::list(5)
This construction generalizes to any combinatorial class that can be defined recursively by a grammar:
>> fiWords := decomposableObjects(
[FiWords = Union(Epsilon,
Atom(B),
Prod(FiWords, Atom(A)),
Prod(FiWords, Atom(A), Atom(B)))
]):
(Note: an {Epsilon} is an object of size 0 while an {Atom} is an object of size 1).
>> fiWords::list(4)
The result is not very readable, but this can be fixed by a quick substitution:
>> map(fiWords::list(4), p -> [eval(subs(p, Prod = id,
Epsilon = null() ))])
Alternatively, we could have provided some extra rewriting rules within the grammar. Notice that the preceding grammar generates the words in an order that is not so obvious. With some small reordering of the grammar, it is possible to ensure that the words are generated in the lexicographic order:
>> fiWords := combinat::decomposableObjects(
[FiWords = Alias(FiWordsRec, DOM_LIST),
FiWordsRec = Union(Epsilon(),
Alias(Prod(Atom(A), FiWordsRec), op),
Atom(B),
Alias(Prod(Atom(B), Atom(A), FiWordsRec), op)
)
]):
fiWords::list(4);
This seems to work nicely. Let us count those words:
>> fiWords::count(i) $ i = 0..10
You will certainly recognize the Fibonacci sequence. Not quite a surprise, the recurrence relation can be seen right away from the grammar. Actually, this recurrence relation is automatically determined by the library, and used for counting efficiently:
>> fiWords::recurrenceRelation() = 0
This also applies for several libraries which are based on {combinat::decomposableObjects}. For example, here is the recurrence relation for binary trees:
>> r := binaryTrees::grammar::recurrenceRelation()
>> assume(n>0):
u(n) = factor(op(solve(r, u(n)),1))
We use Pólya enumeration theory to count unlabelled non oriented graphs on $n$ nodes without loops. To this end, we build the symmetric group $S_n$ seen as the group of the permutations of the $n$ nodes $\protect \T1\textbraceleft i\protect \T1\textbraceright $ of the graphs, and the induced permutation group $G_n$ on the set $E$ of the $\protect \protect \def pdfpageduration{()}\edef {\@genfrac \relax \@@abovewithdelims } {()\z@ }n 2$ possible edges $\protect \T1\textbraceleft i,j\protect \T1\textbraceright $ between those nodes:
>> S4 := Dom::SymmetricGroup(4):
G4 := Dom::PermutationGroupOnSets(S4, 2):
We compute next the cycle indicator of $G_4$. This is a symmetric function which encodes the statistic of the cycle types of the permutations in $G_4$:
>> Z4 := G4::cycleIndicator()
This is to be interpreted as follows: in $G_4$, there are $6=|G_4|\cdot \protect {\begingroup 1\endgroup \@@over 4}$ permutations with one cycle of length $4$ and one cycle of length $2$. The interesting fact about this symmetric function is that, when evaluated on an alphabet $A=(a_1,\protect \global \let \T1\textellipsis .\kern \fontdimen 3\font .\kern \fontdimen 3\font .\kern \fontdimen 3\font \T1\textellipsis ,a_n)$, it returns the generating series by weight for the functions from $E$ to a set of size $n$ whose elements are weighted by $A$. For example, a graph can be seen as a function from $E$ to a set with $2$ elements. Hence, the total number of unlabelled graphs is given by:
>> Z4([1, 1])
Here they are:
>> combinat::graphs::list(4)
>> nops(last(1))
We can refine the counting to get the generating series of unlabelled graphs on $4$ nodes by number of edges:
>> expand(Z4([1, q]))
Double check:
>> map(combinat::graphs::list(4), g -> combinat::graphs::getEdgeNumber(g)/2)
Such computations are carried out in a rather efficient way, so that e.g. counting the number of graphs with 20 nodes takes just a few seconds:
>> (Dom::PermutationGroupOnSets(Dom::SymmetricGroup(20),
2))::cycleIndicator()([1, 1])
Those last computations highlights an important feature of MuPAD-Combinat: \par integration of third-party software (Nauty) \par integration of combinatorial and algebra tools
>> magicSquare :=
proc(n)
begin
[1 = _plus(hold(x).i.j $ i=1..n) $ j=1..n,
1 = _plus(hold(x).i.j $ j=1..n) $ i=1..n,
1 = _plus(hold(x).i.i $ i=1..n),
1 = _plus(hold(x).i.(n+1-i) $ i=1..n)]
end:
>> combinat::LattE::count(magicSquare(4))
>> domain NonDecreasingFunctions(N)
inherits Dom::BaseDomain;
category Cat::CombinatorialClass, Cat::FacadeDomain(DOM_LIST);
axiom Ax::systemRep;
list :=
proc()
option remember;
begin
_concat(combinat::integerVectors::list(i, N,
MinSlope=0,
MinPart=1, MaxPart=N)
$ i=N..N^2);
end_proc;
end:
>> NDF := NonDecreasingFunctions(3):
NDF::list()
>> sequence := [(NonDecreasingFunctions(n))::count() $ n = 1..8]
>> combinat::guess(sequence)[1]
>> [binomial(2*n-1,n) $ n = 1..8]
>> reset():
>> countNDF := combinat::guess([1, 3, 10, 35, 126, 462, 1716])[1]:
>> domain NonDecreasingFunctions(N)
inherits Dom::BaseDomain;
category Cat::CombinatorialClass, Cat::FacadeDomain(DOM_LIST);
axiom Ax::systemRep;
count := () -> countNDF(N-1);
list :=
proc()
option remember;
begin
_concat(combinat::integerVectors::list(i, N,
MinSlope=0,
MinPart=1, MaxPart=N)
$ i=N..N^2);
end_proc;
end:
>> sequence := [(NonDecreasingFunctions(n))::count() $ n = 1..100]
>> domain Algebra(N : Type::NonNegInt,
R = Dom::ExpressionField())
category Cat::FiniteDimensionalAlgebraWithBasis(R);
inherits Dom::FreeModule(R, NonDecreasingFunctions(N));
printTerm := l->_concat(hold(f), op(l));
oneBasis := [$1..N];
mult2Basis :=
proc(part1 : dom::basisIndices, part2 : dom::basisIndices)
local i;
begin
dom::term([part1[part2[i]] $ i=1..N]);
end_proc;
end_domain:
>> setuserinfo(experimental::algTools, 3):
>> (Algebra(1))::representationTheory()
>> (Algebra(2))::representationTheory()
>> (Algebra(3))::representationTheory()
>> (Algebra(4))::representationTheory()
>> (Algebra(5))::representationTheory()
>> examples::
>> experimental::
>> operators::setTensorSymbol("#"):
Sym := examples::SymmetricFunctions():
Sym::s: Sym::Name := hold(Sym): Sym::fixBasesNames():
viewDot(operators::overloaded::dotConversions())
>> QSym := examples::QuasiSymmetricFunctions():
QSym::Name := hold(QSym): QSym::fixBasesNames():
NCSF := examples::NonCommutativeSymmetricFunctions():
NCSF::Name := hold(NCSF): NCSF::fixBasesNames():
viewDot(operators::overloaded::dotConversions())
We start with an example of algebra with several bases. Let $S$ be a finite set, and consider the free module $M$ over the subsets of $S$. It is endowed with an algebra structure by extending the intersection operation by linearity. Implementing this algebra in MuPAD{} requires some helper tools; we put them inside a dummy domain called {SubsetsSpaceTools} to avoid polluting the global name space:
>> domain SubsetsSpaceTools
info_str := "Helper tools for the domain 'SubsetsSpace'";
end_domain:
>> subsetsOf := S -> combinat::subClass(combinat::subsets, Parameters = S):
>> S4 := subsetsOf({1,2,3,4}):
S4::list();
We now implement the module $M$ with elements expanded on the fundamental basis denoted by $F$. There are two parameters: the set {S} and, as usual, the coefficient ring {Ring}. Note the use of {combinat::subClass} to define the combinatorial class of the subsets of {S}:
>> domain SubsetsSpaceTools::Fundamental(S, Ring)
category Cat::AlgebraWithBasis(Ring);
inherits Dom::FreeModule(subsetsOf(S), Ring);
info_str := "The subset space on the fundamental basis";
basisName := hold(F);
mult2Basis :=
proc(s1: dom::basisIndices, s2: dom::basisIndices)
begin
dom::term(s1 intersect s2);
end_proc;
end_domain:
Let us just recall that, in a free module, the entry {dom::basisIndices} contains the combinatorial class that indexes the bases of the module. Here, this is a shortcut for the combinatorial class:
>> domain SubsetsSpaceTools::In(S, Ring)
category Cat::AlgebraWithBasis(Ring);
inherits Dom::FreeModule(subsetsOf(S), Ring);
info_str := "The subset space on the 'In' basis";
basisName := hold(In);
end_domain:
domain SubsetsSpaceTools::Out(S, Ring)
category Cat::AlgebraWithBasis(Ring);
inherits Dom::FreeModule(subsetsOf(S), Ring);
info_str := "The subset space on the 'Out' basis";
basisName := hold(Out);
end_domain:
>> domain SubsetsSpace(S : DOM_SET,
Ring = Dom::Rational : DOM_DOMAIN)
category Cat::ModuleWithSeveralBases(Ring);
inherits Dom::BaseDomain;
info_str := "The subsets space on various bases";
Fundamental := SubsetsSpaceTools::Fundamental(S, Ring);
F := dom::Fundamental; // a shortcut
In := SubsetsSpaceTools::In(S, Ring);
Out := SubsetsSpaceTools::Out(S, Ring);
// When possible, define automatically basis changes by
// transposition or inversion of matrices.
autoDefineBasisChanges := TRUE;
basisChangesBasis := table(
(dom::In, dom::F) =
proc(set : dom::In::basisIndices) : dom::F
local xSet;
begin
dom::F::plus(dom::F::term(xSet) $
xSet in combinat::subsets::list(set));
end_proc);
dual := dom; // The dual of this space.
// The pairs of dual bases.
// The pair [dom::Out, dom::In] will be automatically declared.
dualBasesPairs := {[dom::F, dom::F], [dom::In, dom::Out]};
end_domain:
The crucial line of the preceding code is the declaration of {SubsetsSpace} as a {Cat::ModuleWithSeveralBases}. This category provides helper tools for implementing modules which are represented on several modules. We just need to supply the basis changes from {In} to {F} (see {basisChangesBasis}) and to declare which bases are in duality (see {dual} and {basisChangesBasis}). The system then provides default implementations for the scalar products and the other changes of bases (see {autoDefineBasisChanges}), and provides the standard free module entries {testtype} and {coeffRing} together with the set of bases {bases}. \par We define the free module spanned by the subsets of $\protect \T1\textbraceleft 1,2,3,4\protect \T1\textbraceright $ and build some of its elements:
>> M1234 := SubsetsSpace({1, 2, 3, 4}):
el1 := M1234::F({1, 2});
el2 := M1234::In({1, 2})
The type checking works as usual:
>> testtype(el1, M1234), testtype(el2, M1234)
as well as the bases changes:
>> M1234::In(el1)
>> M1234::Out(el2)
The required matrix inversions are computed only once and remembered, so that later basis changes are considerably faster, at some memory cost. \par Finally we check that algebra products and scalar products are handled correctly:
>> el1*el2
>> operators::scalar(el1, el2)
Products of {Out} elements are actually computed and returned in the {F} basis. As usual, an explicit conversion can be used to force the result back in the {Out} basis:
>> M1234::Out({1, 3, 4})*M1234::Out({2, 3});
>> M1234::Out(last(1))