ZZ:= Integers();
function Pot(T, coeff)
  s:= Nrows(T);
  TT:= Matrix(Rationals(), T)^-1;
  line:= coeff * T;
  M:= Matrix(ZZ, Matrix([ line * T[i] : i in [1..s] ]) * TT);

  PP:= [ 2^(&+Eltseq(M[i])) : i in [1..s] ];
  C:= ChangeRing(Vector(Rationals(), PP) * TT, ZZ);
  return C;
end function;


// Aufgabe 2
G:= Alt(4); 
T:= TableOfMarks(G);
V:= RSpace( ZZ, 5);
Pot(T, V.2+V.3);		// liefert [68,24,12,4,4]

// Alternativ
v:= Pot(T, V.2);
w:= Pot(T, V.3);
M:= [ Solution(T, [ T[i]*T[j] : j in [1..5] ] ): i in [1..5] ];
[ &+[v[i]*w[j]*M[i,j,k]: i,j in [1..5] ]: k in [1..5] ];


// Aufgabe 3
G:= Sym(5);
T:= TableOfMarks(G);
V:= RSpace( ZZ, 19);
X0:= V.17;
X1:= Pot(T, X0);
X2:= Pot(T, X1);
// X2 enthaelt noch 0-en. Einfach 
// X3:= Pot(T, X); eintippen geht nicht in Magma.

// Die Antwort bekommen wir nun trotzdem leicht raus:
Support(X2);
// -> { 1, 2, 3, 6, 7, 10, 12, 13, 15, 17, 19 }

// Also ist Pot(T, V.1) eine G-invariante Teilmenge von
// Pot(T, X2) und Pot(T, V.1) tut's schon.
Support(Pot(T, V.1)) eq {1..19};

// -> liefert true. Also reicht dreimaliges Anwenden.


// Aufgabe 5
function Trees(U)
  if IsEmpty(U) then return [* {} *]; end if;
  return 
    [* < L, w, R > : L in $$(S), 
                     R in $$(U diff Include(S,w)),
                     S in Subsets(Exclude(U, w)),
                     w in U
    *];
end function;
T:= Trees({1,2,3,4});		// Liefert 336 Baeume.

function acton(g, b)
  if b cmpeq {} then return b; end if;
  return < $$(g, b[1]), b[2]^g, $$(g, b[3]) >;
end function;

G:= Sym(4);
R:= [**]; Orbs:= [**];
for b in T do
  if not exists{x: x in Orbs | x cmpeq b} then
    Append(~R, b);
    for g in G do 
      bb:= acton(g, b);
      if not exists{x: x in Orbs | x cmpeq bb} then 
        Append(~Orbs, bb);
      end if;
    end for;
  end if;
end for;
#R;				// -> Liefert 14.

// Das geht natuerlich auch direkt:
// Jede Bahn hat einen "sortierten" Baum als kanonischen Verteter.
function UnlabeledTrees(U)
  if IsEmpty(U) then return [* {} *]; end if;
  return [* < L, U[k], R > : L in $$(U[1..k-1]),
                             R in $$(U[k+1..#U]),
                             k in [1..#U] *];
end function;
#UnlabeledTrees([1..4]);	// -> Liefert auch 14.
