I have a slight variant of this question. I would also appreciate any references for questions like this. (The question is inspired by the study of linear orders in model theory.)
Suppose you're given the following two facts about an unknown linear order:
- $t_1 < \cdots < t_n$
- $s_1 < \cdots < s_m$
We aren't told whether any $t_i$ is identical to $s_j$. The question is: how many possible arrangements of these elements are there, where possibly some of the elements in one list are identical to elements in the other? In other words, if we treat each $t_i$ and $s_j$ as a label (or constant) for some element in a linear order, how many possible arrangement of labels are there that are consistent with the two facts above, assuming we allow that labels might pick out the same element?
That's the question. Here are my thoughts:
If you only count the possible arrangements where all the elements are distinct, the answer (as explained by the link above) is $n+m \choose n$. So the question reduces to how many possible arrangements are there were not all the $t_i$ and $s_j$ are distinct. I'm just having trouble rephrasing the question in the right way.
I think the answer might be the following:
$$\sum_{i = \max(m,n)}^{m+n} {i \choose \min(m,n)} \cdot {\min(m,n) \choose i - \max(m,n)}$$
I came to this roughly by trial-and-error. The first factor is supposed to capture the intuition of "filling $i$ spots". The second factor is meant to capture something like a binomial coefficient to account for the number of identity assignments. For instance, if $m = n = 2$, then the number of such arrangements is:
$${2 \choose 2} + 2\cdot{3 \choose 2} + {4 \choose 2} = 13$$
If $m = 3$ and $n = 2$, the the number of arrangements is:
$${3 \choose 2} + 2\cdot{4 \choose 2} + {5 \choose 2} = 25$$
And if $m = n = 3$, then we get:
$${3 \choose 3} + 3\cdot{4 \choose 3} + 3\cdot{5 \choose 3} + {6 \choose 3} = 63$$
If this is right, how should one intuitively have come by this answer? If it's wrong, what's the answer? Also, generalization to the case where you're given $k$-many facts instead of two would be most welcome!
These are called Delannoy numbers.
An easy way to explain is as follows. Suppose we write down all the $s_i$ and $t_i$ in some order from smallest to largest.
$$s\quad t\quad s\quad s\quad t\quad {s\atop t}\quad t\quad t\quad s\quad t\quad {s\atop t}\quad s$$
Oops! I forgot the subscripts. But that doesn't matter, as they are fully determined by the inequalities we already know. So if $p$ of them are equal, we have:
which can be arranged in $f(m,n,p)=\frac{(m+n-p)!}{p!(m-p)!(n-p)!}$ ways.
So the total number of possible orders is $D(m,n)=\sum_{p=0}^{\min(m,n)}f(m,n,p)$.
Note that $f(m,n,p)$ can be written as $\binom{m}{p}\binom{m+n-p}{m}$. Choose $p$ instances of $s$ to be written above a $t$, and then arrange the result.
A more usual description of the Delannoy numbers is "the number of ways to get from $(0,0)$ to $(m,n)$ on a grid using the steps $(0,1),\ (1,0),$ and $(1,1)$."
Here is a link to the OEIS article, with lots of references and formulas (note the recurrences) and extra information. And of course you can ask Google for more.