Combinatorics: Bijective proof for ${n + t - 1 \choose t - 1} = \sum_{k=0}^n{n-k+t-2 \choose t-2}$ for integers ${n\ge 1}$, ${t\ge 2}$

Question

I am, generally speaking, having issues with proving combinatorics questions using bijective proofs, so any help explaining how to do that in general would be greatly appreciated. I understand why bijective proofs work, but I never know how to start a proof for it. Do I have to define a specific function and then show that it's one-to-one and onto, or is it enough to say that such a function exists? How can I show that it's bijective?

A specific question that I was having issues with is as follows

For integers ${n\ge 1}$, ${t\ge 2}$, use a bijection to prove that: $${n + t - 1 \choose t - 1} = \sum_{k=0}^n{n-k+t-2 \choose t-2}$$

I tried breaking it down: the LHS is just the number of possible multisets with n elements of $t$ types (or the number of $t-1$ element subsets of a set with $n+t-1$ elements). The RHS, on the other hand, for a fixed $k$ gives the number of multisets with $n-k-1$ elements with $t-1$ types.

Now this is where I am unsure of how to continue, i.e. how to define a bijection between these two sets. Some ideas I had:

Let $S$ be the set of all possible $(t-1)$-element subsets of $S' = \{1, 2,\ldots, n+t-1\}$. This represents the LHS. Then let $A$ be the set of all possible $(t-2)$ element subsets of $A' = \{k+1, k+2,\ldots, n + t - 1\}$. Clearly when $k = 0$ then the $A' = S'$. But clearly $|S| \gt |A| $ since $ t-1 \gt t-2$ so I'm not really sure how to continue here. I suppose $ S' = \{1, 2, \ldots , k\}\cup A'$ but I'm not really sure if that helps me.

Any help/hints would be appreciated. Thanks!

Answer 1

I didn't work this out to get a complete proof, but how about looking at an example where $n = 2$ and $t = 4$:

Take $S = \{a,b,c,d,e\}$. If $U$ and $V$ are two subsets of $S$ with $3$ elements we write

$\; U \rho V \;\text{ IF }$
$\quad a \in U \land a \in V$
$\quad a \notin U \land a \notin U \land b \in U \land b \in V$
$\quad a \notin U \land a \notin U \land b \notin U \land b \notin V \land c \in U \land c \in V$

The relation $\rho$ partitions the set of subsets of $S$ with $3$ elements into three blocks containing

$\quad$ ${4 \choose 2}$, ${3 \choose 2}$ and ${2 \choose 2}$ elements.

It looks like we can define a bijection if we first totally order our set with $n + t - 1$ elements.

Answer 2

In bijective proofs I try to start by interpreting the two sides of the equation as counting formulas, which is exactly what you're doing. In some cases, the counting formulas count the same set (in different ways), which is enough for a proof. It is only when the counting formulas count different sets that you need to devise a bijective mapping between the sets. And yes, you would, in general, need to show that the mapping is one-to-one and onto. The first case, where the counting formulas count the same set, is actually the special case of the second in which the bijective mapping is simply the identity.

Now in your problem, you find yourself in the case where both sides count the same thing, as the comment of JMoravitz indicates. The arithmetic interpretation in that comment is equivalent to your multiset interpretation: the $j^\text{th}$ term in the sum corresponds to the number of elements in the multiset of the $j^\text{th}$ type. The only issue that I can see that you're having is that you've only interpreted the right hand side for fixed $k$, when, in fact, $k$ is not fixed—it ranges from $0$ to $n$. Once you interpret $k$ as the number of elements of the multiset of type $1$, and the summand as the number of ways the rest of the multiset could look, you'll be well on your way to a solution.

Answer 3

One method to provide a combinatorial proof is based upon lattice paths. We consider the lattice paths of length $n+t-1$ from $(0,0)$ to $(t-1,n)$ consisting of $(1,0)$-steps and $(0,1)$-steps only. The number of these paths is $$\binom{n+t-1}{t-1}$$ since we have to choose precisely $t-1$ $(1,0)$-steps out of $n+t-1$ steps.

We fix a vertical line going through $(t-2,0)$. Each path from $(0,0)$ to $(t-1,n)$ will cross the line at some point $(t-2,n-k)$ with $0\leq k\leq n$ and the number of these paths is $\binom{n-k+t-2}{t-2}$.

                                           

We can so partition all valid paths by taking paths crossing the line at a specific height $n-k$, followed by a horizontal step to $(t-1,n-k)$ and $k$ vertical steps to $(t-1,n)$.

We conclude \begin{align*} \sum_{k=0}^n\binom{n-k+t-2}{t-2}=\binom{n+t-1}{t-1}\tag{1} \end{align*} and the claim follows.

Note:

• In (1) we count the paths crossing the line $y=t-2$ from top to bottom. We can also count starting from bottom up to top. This means that we change the order of summation in (1) $k\to n-k$ proving thereby \begin{align*} \sum_{k=0}^n\binom{\color{blue}{k}+t-2}{t-2}=\binom{n+t-1}{t-1} \end{align*}