FUNCTION: FreeShuffle - shuffle product in the free algebra

CALLING SEQUENCE:

FreeShuffle(e_1, e_2)

FREE[FreeShuffle](e_1, e_2)

PARAMETERS:

e_1, e_2 = any elements of the free algebra

SYNOPSIS:

• The FreeShuffle function computes the shuffle product of two elements of the free algebra. The function normalizes the result, by essentially collecting coefficients.

• The shuffle of two words w[a, u] and w[b, v] is recursively defined by: FreeShuffle(w[a,u], w[b,v]) = FreeConcat(w[a], FreeShuffle(w[u],w[b,v])) + FreeConcat(w[b], FreeShuffle(w[a,u], w[v]) and FreeShuffle(w[], w[c]) = FreeShuffle(w[c], w[]) = c.

• One can add the extra argument 'q' to compute the q-shuffle product. It defined on words by: FreeShuffle(w[a,u], w[b,v], 'q') = FreeConcat(w[a], FreeShuffle(w[u],w[b,v], 'q') + q^(nops([a,u])) * FreeConcat(w[b], FreeShuffle(w[a,u], w[v], 'q').

• Whenever there is a conflict between the function name FreeShuffle and another name used in the same session, use the long form FREE['FreeShuffle'].

EXAMPLES:

> with(FREE):
> FreeShuffle(w[1,2] + w[2,1], w[1,2,1]);
 
        4 w[1, 2, 1, 2, 1] + 4 w[1, 1, 2, 2, 1] + 2 w[1, 1, 2, 1, 2]
 
      + 2 w[1, 2, 1, 1, 2] + 2 w[2, 1, 1, 2, 1] + 2 w[2, 1, 2, 1, 1]
 
      + 4 w[1, 2, 2, 1, 1]
 
> FreeShuffle(w[1,2], w[2,1], 'q');
 
                  2                   3    4
                 q  w[2, 1, 2, 1] + (q  + q ) w[2, 1, 1, 2]
 
                                          2
               + (1 + q) w[1, 2, 2, 1] + q  w[1, 2, 1, 2]