Shuffle product of words

See also

The module sage.combinat.shuffle contains a more general implementation of shuffle product.

class sage.combinat.words.shuffle_product.ShuffleProduct_shifted(w1, w2)

Bases: sage.combinat.words.shuffle_product.ShuffleProduct_w1w2

Shifted shuffle product of w1 with w2.

This is the shuffle product of w1 with the word obtained by adding the length of w1 to every letter of w2.

Note that this class is meant to be used for words; it misbehaves when w1 is a permutation or composition.

EXAMPLES:

sage: from sage.combinat.words.shuffle_product import ShuffleProduct_shifted
sage: w, u = Word([1,2]), Word([3,4])
sage: S = ShuffleProduct_shifted(w,u)
sage: S == loads(dumps(S))
True
class sage.combinat.words.shuffle_product.ShuffleProduct_w1w2(w1, w2)

Bases: sage.combinat.combinat.CombinatorialClass

The shuffle product of the two words w1 and w2.

If \(u\) and \(v\) are two words, then the shuffle product of \(u\) and \(v\) is a certain multiset of words defined as follows: Let \(a\) and \(b\) be the lengths of \(u\) and \(v\), respectively. For every \(a\)-element subset \(I\) of \(\{1, 2, \cdots, a+b\}\), let \(w(I)\) be the length-\(a+b\) word such that:

  • for every \(1 \leq k \leq a\), the \(i_k\)-th letter of \(w(I)\) is the \(k\)-th letter of \(u\), where \(i_k\) is the \(k\)-th smallest element of \(I\);
  • for every \(1 \leq l \leq b\), the \(j_l\)-th letter of \(w(I)\) is the \(l\)-th letter of \(v\), where \(j_l\) is the \(l\)-th smallest element of \(\{1, 2, \cdots, a+b\} \setminus I\).

The shuffle product of \(u\) and \(v\) is then the multiset of all \(w(I)\) with \(I\) ranging over the \(a\)-element subsets of \(\{1, 2, \cdots, a+b\}\).

EXAMPLES:

sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2
sage: W = Words([1,2,3,4])
sage: s = ShuffleProduct_w1w2(W([1,2]),W([3,4]))
sage: sorted(list(s))
[word: 1234, word: 1324, word: 1342, word: 3124, word: 3142, word: 3412]
sage: s == loads(dumps(s))
True

sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([2]))
sage: sorted(list(s))
[word: 1243, word: 1423, word: 1432, word: 2143]

sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([]))
sage: sorted(list(s))
[word: 143]
cardinality()

Return the number of words in the shuffle product of w1 and w2.

This is understood as a multiset cardinality, not as a set cardinality; it does not count the distinct words only.

It is given by \(\binom{l_1+l_2}{l_1}\), where \(l_1\) is the length of w1 and where \(l_2\) is the length of w2.

EXAMPLES:

sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2
sage: w, u = map(Words("abcd"), ["ab", "cd"])
sage: S = ShuffleProduct_w1w2(w,u)
sage: S.cardinality()
6

sage: w, u = map(Words("ab"), ["ab", "ab"])
sage: S = ShuffleProduct_w1w2(w,u)
sage: S.cardinality()
6