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:
- If $\#\mathcal{C}\ne \#\mathcal{A}+\#\mathcal{B}$, then $c_{\mathcal{A},\mathcal{B},\mathcal{C}}=0$.
- We have an upper bound $c_{\mathcal{A},\mathcal{B},\mathcal{C}}\le \binom{\#\mathcal{A}+\#\mathcal{B}}{\#\mathcal{A}}$
- 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?