1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.