Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recall that in the section on functions, we created an encoding for the paths from the point $(0, 0)$ to the point $(m, n)$ which either went right or up at each step. In particular, we said that each path can be represented as a bit string of length $m+ n$ with exactly $m$ 0's and $n$ 1's.

For this problem, let $m = 8, n = 5$.

a. How many paths are there from $(0, 0)$ to $(8, 5)$?

b. How many of these paths go through the point $(3, 3)$?

c. How many of them avoid the point $(3, 3)$?

share|improve this question
4  
Unless I miss my guess, you have copied out a problem from some source without attribution, which constitutes plagiarism. Please let us know where this problem comes from; why it's worth working on; what progress you have made on it. If it's homework, please add the "homework" tag. –  Gerry Myerson Jul 29 '12 at 23:56
    
See also math.stackexchange.com/questions/12093/… –  Gerry Myerson Jul 29 '12 at 23:59
1  
I got this question from one of my university professor website. the univ is UWM. I have a Qualifying exam this September and I am solving as much as I can from Discrete mathematics. the source is : –  Sam Jul 30 '12 at 0:02
    
cs.uwm.edu/classes/cs317 –  Sam Jul 30 '12 at 0:02
1  
@Raphael: Not quite, since here there's no restriction about staying below the diagonal. –  Hans Lundmark Jul 30 '12 at 9:26

2 Answers 2

Hints:

a. How many ways are there of arranging eight $0$s and five $1$s in a string?

b. How many ways are there of arranging three $0$s and three $1$s in a string? How many ways are there of arranging five $0$s and two $1$s in a string? How many ways are there of arranging three $0$s and three $1$s followed by five $0$s and two $1$s?

c. How is this related to a and b?

share|improve this answer

I recommend googling the Binomial theorem, as it's an introduction to binomial coefficients. Going from (0,0) to (m,n) is one of the basics of probability. The answer to your question is; $\frac {n!} {k!*(n-k)!}$; n choose k

enter image description here

n in this case would be te sum of the lines needed to make a path; m+n, and k would be either horizontal of vertical, so m or n

$\frac {n!} {k!*(n-k)!}$ becomes $\frac {(m+n)!} {m!*n!}$

For things like "going through (3,3)", you could use m = 3, n = 3 to go to (3,3) and multiply that by "going from (3,3) to (8-3, 5-3)", which is the same as using $\frac {(m+n)!} {m!*n!}$ again with m = 8-3, n = 5-3

share|improve this answer
    
Thanks for pointing out, before I added MathJax, it was (m+n)!, I must have accidentally deleted it. –  Kloppie5 Apr 24 at 21:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.