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$

0

You must log in to answer this question.

Browse other questions tagged .