For context, I was trying to find in how many differnt ways one could join two lists of length m and n whilst preserving their internal order. So, for example, a list of length 1 $\langle 1 \rangle$ and a list of length 4 $\langle2, 3, 4, 5\rangle$ can be combined in five possible ways $\langle 1, 2, 3, 4, 5\rangle, $ $\langle 2, 1, 3, 4, 5\rangle, $ $\langle 2, 3, 1, 4, 5\rangle,$ $\langle 2, 3, 4, 1, 5\rangle, $ $\langle 2, 3, 4, 5, 1\rangle $
And two lists of length 2 $\langle 1,2\rangle$ en $\langle 3,4\rangle$ could be joined in 6 ways. $\langle 1,2,3,4\rangle,$ $\langle 1,3,2,4\rangle,$ $\langle 1,3,4,2\rangle,$ $\langle 3,4,1,2\rangle,$ $\langle 3,1,4,2\rangle,$ $\langle 3,1,2,4\rangle $
For this I came with the equation* $$\sum_{i=0}^{n-1} {n-1 \choose i} {m+1 \choose i+1}$$ Which when plugged into WolframAlpha gives $$\frac{(m+n)!}{m!n!}$$
And for all the my test cases, these two do indeed give the same result. So, my question is, what is it that makes these two equations be equivalent? I am supposing it has something to do with turning ${n \choose k}$ into $\frac{n!}{k!(n-k)!}$ but I wouldn't know how to continue due to the summation sign.
*'Proof' of the formula: I make $i$ cuts in the list of length n so as to divide it into $i+1$ pieces. The number of different ways I could make such a cut is ${n-1 \choose i}$. I then insert these pieces into the list of length m this can be done in ${m+1 \choose i+1}$ ways. So when making $i$ cuts I can join the strings in ${n-1 \choose i} {m+1 \choose i+1}$ ways. I can make up to $n-1$ cuts into the list so we should sum the number of combinations for every possible number of cuts resulting in $\sum_{i=0}^{n-1} {n-1 \choose i} {m+1 \choose i+1}$