In this posting, OP asks a proof of the following identity
$$ \sum_{k=0}^{n} \binom{tk+r}{k}\binom{t(n-k)+s}{n-k} \frac{r}{tk+r} = \binom{tn+r+s}{n} \tag{1} $$
for non-negative integers $t, n, r, s$ with $t, n \geq 1$. I would like to reformulate this question in terms of probability. Here is my try:
Setting. Let $(\Omega, 2^{\Omega}, \mathbb{P})$ be the probability space where
- $\Omega = \{ \omega \subseteq [tn+r+s] : |\omega| = n\}$ is the family of all subsets of $[tn+r+s]$ with size $n$, and
- $\mathbb{P}$ is the law of uniform distribution on $\Omega$, i.e., $\mathbb{P}(\{\omega\}) = \frac{1}{|\Omega|}$ for each $\omega \in \Omega$.
Then define random variables $S_k$ and $T$ on $\Omega$ by
- $S_k(\omega) = \left|\omega\cap[tk+r]\right|$, for $k = 0, \cdots, n$,
- $T(\omega) := \min\{ k \geq 0 : S_k(\omega) = k \}$.
$\hspace{9em}$
Since $k \mapsto S_k(\omega)$ is a non-decreasing function from $\{0,\cdots,n\}$ to itself, this map has a fixed point and the above definition makes sense. Then I am interested the following claim:
Claim. We have $$ \mathbb{P}(T = k) = \frac{r}{tk+r} \frac{\binom{tk+r}{k}\binom{t(n-k)+s}{n-k}}{\binom{tn+r+s}{n}}. \tag{2} $$
Given this claim, the identity $\text{(1)}$ is simply $1 = \mathbb{P}(T < \infty) = \sum_{k=0}^{n} \mathbb{P}(T = k) $. I checked this claim for various values of $t, n, r, s$ but was unable to establish a proof.
So, here is a question: Although there is a proof using complex analysis in the original posting, I would be happy to know whether a probabilistic or combinatorial proof of $\text{(1)}$ or $\text{(2)}$ is available, not necessarily based on the setting above.
It might be helpful to note that $\text{(2)}$ is equivalent to proving the following problem:
For each $k$, the number of subsets $A$ of $[tk+r]$ satisfying $|A| = k$ and $|A\cap[tj+r]| > j$ for all $j<k$ is given by $\frac{r}{tk+r}\binom{tk+r}{k}$.
This sounds like a generalization of Catalan numbers, although I have no good idea for this.
The starting identity a consequence of the Rothe-Hagen identity. Micheal Spivey wrote an interesting post about it in his blog and combinatorial proofs from Wenchang Chu are freely available here.