shuffle

The term ‘shuffle’ conjures up the idea of shuffling a pack of cards. In fact the mathematical idea is nearer to shuffling two packs of cards one through the other. Suppose we have a pack of $p$ cards and a pack of $q$ cards and we build a pack of $p+q$ cards, whilst retaining the order on the two ‘sub-packs’. The result is a $(p,q)$-shuffle.

For $p,q \in \mathbb{N}$ two natural numbers, a **$(p,q)$-shuffle** is a permutation

$(\mu_1, \cdots, \mu_p, \nu_1, \cdots, \nu_q)$

of $(1,2, \cdots, p+q)$ subject to the condition that

$\mu_1 \lt \mu_2 \lt \cdots \lt \mu_p$

and

$\nu_1 \lt \nu_2 \lt \cdots \lt \nu_q
\,.$

The **signature** of a $(p,q)$-shuffle is the signature of the corresponding permutation.

Two other equivalent (and dual) ways of defining the notion of $(p,q)$-shuffle are as follows (e.g. Hoffbeck-Moerdijk 17, section 1.1):

- Consider $p$ and $q$ as the linear orders $[1,p] = \{ 1 \lt \dots \lt p \}$ and $[1,q] = \{ 1 \lt \dots \lt q \}$. Then a $(p,q)$-shuffle is a way of extending the partial order on the coproduct $[1,p] + [1,q]$ to a linear order, or equivalently, a surjective monotone function$[1,p] + [1,q] \to [1,p+q].$
- Consider $p$ and $q$ as non-empty linear orders $[0,p] = \{ 0 \lt \dots \lt p \}$ and $[0,q] = \{ 0 \lt \dots \lt q \}$. Then a $(p,q)$-shuffle is a maximal chain? within the product partial order $[0,p] \times [0,q]$, or equivalently, an injective monotone function$[0,p+q] \to [0,p] \times [0,q].$

The same concept viewed from the other end leads to *unshuffles* . These are just shuffles but are used in dual situations in the applications. The definition that follows is ‘from the literature’. It is equivalent to that of shuffle that we gave above. (Although not needed, it is important to note the different terminology used in certain applications of the idea for when original source material is consulted.)

We say that a permutation $\sigma\in S_n$ is a $(j,n-j)$-unshuffle, $o\leq j\leq n$ if $\sigma(1)\lt \ldots \sigma(j)$ and $\sigma(j+1)\lt \ldots \lt \sigma(n)$.

You can also say that $\sigma$ is a $(j,n-j)$-unshuffle if $\sigma(i) \lt \sigma(i+1)$ when $i\neq j$.

Shuffles control the combinatorics of products of simplices. See products of simplices for details.

Related to the product of simplices: shuffles control the Eilenberg-Zilber map. See there for details.

Shuffles are used in defining the pre-cgc structure on $\bigwedge V$ in the theory of differential graded coalgebras

Shuffles are also used for defining the shuffle product on $T(V)$, see differential graded Hopf algebra.

In the definition of L-∞ algebras the *unshuffle* side of shuffles is used.

$(p,q)$-shuffles (called *$(s,t)$-permutations*) are discussed in section 2.2.3 of

- Marcelo Aguiar, Swapneel Mahajan,
*Monoidal Functors, Species and Hopf Algebras*, With forewords by Kenneth Brown, Stephen Chase, André Joyal. CRM Monograph Series**29**Amer. Math. Soc. 2010. lii+784 pp. (author pdf)

The two dual equivalent characterizations of $(p,q)$-shuffles (called *shuffles of linear trees* or *shuffles of linear orders*) are discussed in section 1.1 of

- Eric Hoffbeck, Ieke Moerdijk,
*Shuffles of trees*, (arXiv:1705.03638).

Revised on October 23, 2017 08:04:14
by Noam Zeilberger
(81.253.14.171)