In the exercises below, we assume that the package has been loaded with:
>> package("Combinat"):
Also, to save some typing, we recommend to export the combinat library:
>> export(combinat):
Exercise:
combinat::partitions::list
with MaxSlope
.
combinat::integerVectors::list
with MaxPart
; also try
out i^3 $ i=1..5
, and use _concat
. Exercise:
Draw all the Dyck paths of length 6. Hint: use map
,
combinat::dyckWords::list
, and
combinat::dyckWords::printPretty
.
Exercise:
List all the Motzkin paths of length 6 (a Motzkin path is similar
to a Dyck path, except that horizontal steps are allowed). Hint: use
combinat::integerVectors
.
Exercise:
Draw all the tableaux of size 4. Hint: use
combinat::partitions::list
, combinat::tableaux::list
and
combinat::tableaux::printPretty
.
Exercise:
Count the number of partitions of 1000 with parts bounded below by
10. Hint: first try out how far you can go with
combinat::partitions
. Then, switch to
combinat::decomposableObject
and use Multiset
,
Sequence
, and MinLength
. Hint: check the examples of use
of combinat::decomposableObject
in the guided tour.
Exercise: Try and analyze the following piece of code:
>> (g := combinat::partitions::generator(4);
while (p := g()) <> FAIL do
print(p, combinat::partitions::printPretty(p))
end_while)
Exercise:
>> makeGen :=
proc()
option escape;
local i;
begin
i := 0;
proc() begin i:=i+1; end;
end:
g:=makeGen():
g(), g(), g(), g(), g()
1, 8, 27, ...
combinat::generators::fromNext
and
combinat::generators::map
.
Exercise:
combinat::generators::pipe
.
n
which returns a
generator for all the Motzkin words of length n
. Hint: use
closures and don't forget the escape option.
Exercise:
[1,4,3,2]
.
Hint: use combinat::permutations::inversionsNumber
and
combinat::permutations::hasPattern
, and try out the
following examples:
>> select([1,2,3,4,5,6,7,8], not isprime);
Evaluate the complexity in time and memory of this computation.
combinat::generators::select
, and try
out this example:
>> makeAverager :=
proc()
option escape;
local sum,n;
begin
sum:=0;
n:=0;
proc(x)
begin
if args(0) = 0 then // call without argument
sum/n
else
sum := sum + x; // call with one argument
n := n + 1;
end_if;
end_proc;
end_proc:
g := makeAverager(): // create a new averager
g(1),g(5),g(0),g(10): // accumulate the numbers
g(); // return their average
Exercise:
ShuffleAlgebra
on compositions. Hint: look
for the implementation of FreeAlgebra
in the guided tour,
use combinat::words::shuffle
, and try out
>> _plus(x^i $ i in [1,5,6,8])
coconcat(u)
that returns the list
of all the couples of words v and w such that u=v.w:
>> coconcat([1, 2, 3])
[[[], [1, 2, 3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3], []] ]
Cat::HopfAlgebraWithBasis
) by inserting the following
method:
>> coproductBasis :=
proc(u: words) : ShuffleAlgebra
local v;
begin
_plus(dom::tensorAlgebra(v) $ v in coconcat(u))
end_proc:
You can now compute the coproduct of any element of the algebra
using operators::coproduct
, and reciprocally use
operators::mu
to compute the image in ShuffleAlgebra
of any element of S⊗S via the product. You may wish to
issue:
>> export(operators, coproduct, mu):
ShuffleAlgebra
into a graded
Hopf algebra (Cat::GradedHopfAlgebraWithBasis
), and write a
procedure that checks systematically the compatibility of the
product and coproduct up to a given degree.
The Iwahori-Hecke algebra Hn(q) is the C-algebra
generated by elements Ti for i<n with the relations:
2
T_i^2=(q-1)T_i+q for 1≤i ≤n-1,
T_iT_j=T_jT_i for |i-j|>1,
T_iT_i+1T_i =T_i+1T_iT_i+1T for 1≤i ≤n-2,
The 0-Hecke algebra is obtained by setting q=0 in these relations. Then,
the first relation becomes Ti2=-Ti. Let πi := 1+Ti.
combinat::subClass
to define the combinatorial class
of the permutations of n.
HeckePi(n)
for the Hecke algebra
in the basis (πσ)σ∈ Sn with coefficient
the rational (Dom::rational
).
HeckeT(n)
for the Hecke algebra
in the basis (Tσ)σ∈ Sn with coefficient
the rational (Dom::rational
).
permutations::smallerBruhat
). Make
the conversion automatic.
Dom::ExpressionField()
. Modify the two parameterized domains
HeckePi(n)
and HeckeT(n)
so that they accept a ring for second
parameter with Dom::ExpressionField()
as default value.
trace
that compute the trace of the endomorphism
x∈Hn(0) →x e where e∈Hn(0).
radNormal
that normalize an element of Hn(0)
modulo its radical.
Alg
. The basis B of A is indexed by the element of
the domain Alg::basisIndices
. Like all combinatorial domain this domain may
have a list method which can be called by Alg::basisIndices::list
.
GetBasis
to compute a basis of an algebra or more
generally of a free module.
Generic Element
to compute a generic element;
Radical
to compute the radical of an algebra.
MuPAD Combinat, an open source algebraic combinatorics package