1
$\begingroup$

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)$?

$\endgroup$
7
  • 4
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jul 29, 2012 at 23:56
  • $\begingroup$ See also math.stackexchange.com/questions/12093/… $\endgroup$
    – Gerry Myerson
    Jul 29, 2012 at 23:59
  • 1
    $\begingroup$ 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 : $\endgroup$
    – Sam
    Jul 30, 2012 at 0:02
  • $\begingroup$ cs.uwm.edu/classes/cs317 $\endgroup$
    – Sam
    Jul 30, 2012 at 0:02
  • 1
    $\begingroup$ @Raphael: Not quite, since here there's no restriction about staying below the diagonal. $\endgroup$
    – Hans Lundmark
    Jul 30, 2012 at 9:26

2 Answers 2

Reset to default
5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for pointing out, before I added MathJax, it was (m+n)!, I must have accidentally deleted it. $\endgroup$
    – Kloppie5
    Apr 24, 2014 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .