The shuffle product of words of lengths
m and
n is a sum over the ways of interleaving the two words, as shown in the following examples: :
ab ⧢
xy =
abxy +
axby +
xaby +
axyb +
xayb +
xyab :
aaa ⧢
aa = 10
aaaaa It may be defined inductively by :
u ⧢ ε = ε ⧢
u =
u :
ua ⧢
vb = (
u ⧢
vb)
a + (
ua ⧢
v)
b where ε is the
empty word,
a and
b are single elements, and
u and
v are arbitrary words. The shuffle product was introduced by . The name "shuffle product" refers to the fact that the product can be thought of as a sum over all ways of
riffle shuffling two words together: this is the
riffle shuffle permutation. The product is
commutative and
associative. The shuffle product of two words in some alphabet is often denoted by the
shuffle product symbol ⧢ (
Unicode character U+29E2 , derived from the
Cyrillic letter
sha). ==Infiltration product==