# Shuffling unordered partitions

Consider the following:

• Let $$\mathcal{A}$$ be an unordered partition of $$\{1,\dotsc,p\}$$,
• Let $$\mathcal{B}$$ be an unordered partition of $$\{1,\dotsc,q\}$$
• Let $$\mathcal{C}$$ be an unordered partition of $$\{1,\dotsc,p+q\}$$.

A shuffle is a bijection $$\sigma:\{1,\dotsc,p\}\sqcup\{1,\dotsc,q\}\to \{1,\dotsc,p+q\}$$ monotone on both summands. Let $$\mathrm{Sh}(p,q)$$ be the set of them. Obviously $$\#\mathrm{Sh}(p,q)=\binom{p+q}{p}$$. For a shuffle $$\sigma$$, we have an unordered partition $$\sigma(\mathcal{A})\cup \sigma(\mathcal{B})$$ of $$\{1,\dotsc,p+q\}$$. I am interested in the following number $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}:=\#\{\sigma\in\mathrm{Sh}(p,q);\,\sigma(\mathcal{A})\cup\sigma(\mathcal{B}) = \mathcal{C}\}.$$ There are some simple first observations:

1. If $$\#\mathcal{C}\ne \#\mathcal{A}+\#\mathcal{B}$$, then $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}=0$$.
2. We have an upper bound $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}\le \binom{\#\mathcal{A}+\#\mathcal{B}}{\#\mathcal{A}}$$
3. The only difficulty arises if there are $$A\in\mathcal{A}$$ and $$B\in\mathcal{B}$$ with the same cardinality, otherwise $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}=1$$.

Is there an easy combinatorial formula for $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}$$ which I’m missing? I am particularly interested in the question: When is $$c_{\mathcal{A},\mathcal{B},\mathcal{C}}$$ even?