combinatorics
I have been assigned the following homework problem:
Let $f(m,n)$ be the number of north-east lattice paths which exist from $(0,0)$ to $(m,n)$.
(i) Show that $f(m,n) = f(m-1,n) + f(m,n-1)$.
(ii) Show by induction that $f(m,n) = \binom{n+m}{n}$.
I've been reading around (the concept of north-east lattice paths is entirely new to me), but still cannot seem to wrap my head around an approach to this problem. Any help would be greatly appreciated!
Divide by $4^n$ so that the identity reads (again, for $n$ even)
$$ \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}. \tag{1}$$
Claim 1: Select a permutation $\sigma$ of $[n]$ uniformly at random. For each cycle $w$ of $\sigma$, color $w$ red with probability $1/2$; otherwise, color it blue. This creates a colored permutation $\sigma_C$. Then $$\binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n}$$ is the probability that exactly $k$ of the $n$ elements of a randomly-chosen permutation $\sigma$ are colored red. (See proof of Claim 1 below.)
Claim 2: Select a permutation $\sigma$ of $[n]$ uniformly at random. Then, if $n$ is even, $$\frac{1}{2^n} \binom{n}{n/2}$$ is the probability that $\sigma$ contains only cycles of even length. (See proof of Claim 2 below.)
Combinatorial proof of $(1)$, given Claims 1 and 2: For any colored permutation $\sigma_C$, find the smallest element of $[n]$ contained in an odd-length cycle $w$ of $\sigma_C$. Let $f(\sigma_C)$ be the colored permutation for which the color of $w$ is flipped. Then $f(f(\sigma_C)) = \sigma_C$, and $\sigma_C$ and $f(\sigma_C)$ have different parities for the number of red elements but the same probability of occurring. Thus $f$ is a sign-reversing involution on the colored permutations for which $f$ is defined. The only colored permutations $\sigma_C$ for which $f$ is not defined are those that have only even-length cycles. However, any permutation with an odd number of red elements must have at least one odd-length cycle, so the only colored permutations for which $f$ is not defined have an even number of red elements. Thus the left-hand side of $(1)$ must equal the probability of choosing a colored permutation that contains only even-length cycles. The probability of selecting one of the several colored variants of a given uncolored permutation $\sigma$, though, is that of choosing an uncolored permutation uniformly at random and obtaining $\sigma$, so the left-hand side of $(1)$ must equal the probability of selecting a permutation of $[n]$ uniformly at random and obtaining one containing only cycles of even length. Therefore, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}.$$
(Clearly, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} = 1,$$ which gives another combinatorial proof of the unsigned version of $(1)$ mentioned in the question.)
Proof of Claim 1: There are $\binom{n}{k}$ ways to choose which $k$ elements of a given permutation will be red and which $n-k$ elements will be blue. Given $k$ particular elements of $[n]$, the number of ways those $k$ elements can be expressed as the product of $i$ disjoint cycles is $\left[ {k \atop i} \right]$, an unsigned Stirling number of the first kind. Thus the probability of choosing a permutation $\sigma$ that has those $k$ elements as the product of $i$ disjoint cycles and the remaining $n-k$ elements as the product of $j$ disjoint cycles is $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right] /n!$, and the probability that the $i$ cycles are colored red and the $j$ cycles are colored blue as well is $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right]/(2^i 2^j n!).$ Summing up, the probability that exactly $k$ of the $n$ elements in a randomly chosen permutation are colored red is \begin{align} \frac{\binom{n}{k}}{n!} \sum_{i=1}^k \sum_{j=1}^{n-k} \frac{\left[ {k \atop i} \right] \left[ n-k \atop j \right]}{2^i 2^j} = \frac{\binom{n}{k}}{n!} \sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} \sum_{j=1}^{n-k} \frac{\left[ {n-k \atop j} \right]}{2^j}. \end{align} The two sums are basically the same, so we'll just do the first one. $$\sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} = \left( \frac{1}{2} \right)^{\overline{k}} = \prod_{i=0}^{k-1} \left(\frac{1}{2} + i\right) = \frac{1 (3) (5) \cdots (2k-1)}{2^k} = \frac{1 (2) (3) \cdots (2k-1)(2k)}{2^k 2^k k!} = \frac{(2k)!}{4^k k!}.$$ (The first equality is the well-known property that Stirling numbers of the first kind are used to convert rising factorial powers to ordinary powers. This property can be proved combinatorially. For example, Vol. 1 of Richard Stanley's Enumerative Combinatorics, 2nd ed., pp. 34-35 contains two such combinatorial proofs.)
Thus the probability that exactly $k$ of the $n$ elements of a randomly chosen permutation are colored red is $$\frac{\binom{n}{k}}{n!} \frac{(2k)!}{4^k k! } \frac{(2n-2k)!}{4^{n-k} (n-k)!} = \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n}.$$
Proof of Claim 2: Since there can be no odd cycles, $\sigma(1) \neq 1$. Thus there are $n-1$ choices for $\sigma(1)$. We have already chosen the element that maps to $\sigma(1)$, but otherwise there are no restrictions on the value of $\sigma(\sigma(1))$, and so we have $n-1$ choices for $\sigma(\sigma(1))$ as well.
Now $n-2$ elements are unassigned. If $\sigma(\sigma(1)) \neq 1$, then we have an open cycle. We can't assign $\sigma^3(1) = 1$, as that would close the current cycle at an odd number of elements. Also, $\sigma(1)$ and $\sigma^2(1)$ are already taken. Thus there are $n-3$ choices for the value of $\sigma^3(1)$. If $\sigma(\sigma(1)) = 1$, then we have just closed an even cycle. Selecting any unassigned element in $[n]$, say $j$, we cannot have $\sigma(j) = j$, as that would create an odd cycle, and $1$ and $\sigma(1)$ are already taken. Thus we have $n-3$ choices for $\sigma(j)$ as well.
In general, if there are $i$ elements unassigned and $i$ is even, there is either one even-length open cycle or no open cycles. If there is an open cycle, we cannot close it, and so we have $i-1$ choices for the next element in the cycle. If there is not an open cycle, we select the smallest unassigned element $j$. Since we cannot have $\sigma(j) = j$, there are $i-1$ choices for $\sigma(j)$. Either way, we have $i-1$ choices. If there are $i$ elements unassigned and $i$ is odd, though, there must always be an odd-length open cycle. Since we can close it, there are $i$ choices for the next element in the cycle.
All together, then, if $n$ is even then the number of permutations of $[n]$ that contain only cycles of even length is $$(n-1)^2 (n-3)^2 \cdots (1)^2 = \left(\frac{n!}{2^{n/2} (n/2)!}\right)^2 = \frac{n!}{2^n} \binom{n}{n/2}.$$ Thus the probability of choosing a permutation uniformly at random and obtaining one that contains only cycles of even length is $$\frac{1}{2^n} \binom{n}{n/2}.$$
(I've been thinking about this problem off and on for the two months since I first posted it. What finally broke it open for me was discovering the interpretation of the unsigned version of the identity mentioned as #60 on Richard Stanley's "Bijective Proof Problems" document.)
U corresponds to ( and R corresponds to ). If you cross the diagonal, then at the first point after you cross the diagonal, you have more R's than U's, so you have more ) than ( so the sequence can no longer be completed to a sequence of balanced parentheses. For example, URR becomes ()) which is unbalanced.
Best Answer
Assuming $m,n >0$, we have the picture below. The only ways to get to $(m,n)$ are to start at $(m-1,n)$ and go east or start at $(m,n-1)$ and go north.
Since the last segment of the path is distinct, for $m,n>0$ we have $f(m,n) = f(m-1,n)+f(m,n-1)$.
If $m=0$ and $n>0$, we see that there is only one path and $f(0,n) = n$. Similarly, $f(m,0) = m$.
Using induction, we see that once we specify the south west boundary values, that all the other values are uniquely defined.
It is easy to check that $f(0,n) = \binom{n}{n}$ and $f(m,0) = \binom{m}{m}$, and since $\binom{n+m}{n} = \binom{n+m-1}{n} + \binom{n+m-1}{n-1} $, we see that $g(m,n) = \binom{n+m}{n}$ satisfies the difference equation and the boundary conditions, hence $f=g$.