Starting at $(0, 0)$, Richard takes $2n+1$ steps, with each step being one unit either East, North, West, or South. For each step, the direction is chosen uniformly at random from the four possibilities. Determine the probability that Richard ends at $(1, 0)$.
Problem
Source: Canada RepĂȘchage 2016/7
Tags: combinatorics, counting, probability
19.06.2016 04:54
19.06.2016 04:57
19.06.2016 05:06
lucasxia01 wrote:
Don'you have to think about how many there are turning ways for each $N$,$S$,$E$,$W$?
19.06.2016 05:10
yes, I have fixed my solution but there doesn't seem to be a plausible way that I know of evaluating that summation.
19.06.2016 05:17
lucasxia01 wrote: yes, I have fixed my solution but there doesn't seem to be a plausible way that I know of evaluating that summation. You're final answer should be $\boxed{\frac{\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}}{4^{2n+1}}}$, I think.
19.06.2016 05:24
I fixed it with WolframAlpha but I don't know how else to solve this problem...
19.06.2016 05:29
lucasxia01 wrote: I fixed it with WolframAlpha but I don't know how else to solve this problem... You have already solved the problem,$\boxed{\frac{\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}}{4^{2n+1}}}$should't be changed anymore, I think...
19.06.2016 05:33
Are the answers of this contest (it is a contest I presume?) in any form?
19.06.2016 05:39
lucasxia01 wrote: Are the answers of this contest (it is a contest I presume?) in any form? I want to know too
19.06.2016 05:54
lucasxia01 wrote:
A way to compute this sum. We have $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}.$$Note that by Vandermonde's identity we have $$\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}= \binom{2n+1}{n}.$$Therefore, $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}^2.$$Thus, the answer is $\frac{\binom{2n+1}{n}^2}{4^{2n+1}}$, which is the same as DIffCALCFTW's answer.
19.06.2016 06:11
shinichiman wrote: lucasxia01 wrote:
A way to compute this sum. We have $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}.$$Note that by Vandermonde's identity we have $$\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}= \binom{2n+1}{n}.$$Therefore, $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}^2.$$Thus, the answer is $\frac{\binom{2n+1}{n}^2}{4^{2n+1}}$, which is the same as DIffCALCFTW's answer. Yes! You are right! Thinking arranging $2n+1$ cards,which consists of $4$ kinds(Let $A$,$B$,$C$,$D$). You have to put $n$ cards of either $A$ or$B$,and same as to $C$or$D$. But you have to put $A$ one more than other three cards. So, the number of arrangements is $({}_{2n+1}C_{n})^{2}$
19.06.2016 08:19
Yes, you guys are correct. Thank you @shinichiman for elaborating on using Vandermonde's identity.