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

  • 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.2012-07-29
  • 0
    See also http://math.stackexchange.com/questions/12093/counting-number-of-moves-on-a-grid?rq=12012-07-29
  • 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 :2012-07-30
  • 0
    http://www.cs.uwm.edu/classes/cs317/2012-07-30
  • 0
    These things are called [Dyck paths](https://en.wikipedia.org/wiki/Dyck_path#Applications_in_combinatorics).2012-07-30
  • 1
    @Raphael: Not quite, since here there's no restriction about staying below the diagonal.2012-07-30
  • 0
    @HansLundmark: True, my mistake.2012-07-30

2 Answers 2