1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatoric problem

Tags:
  1. Feb 1, 2016 #1
    We have a square grid. In how many ways we get to the point [20,30], if we can not get points [5,5], [15,10] [15,10] [17,23]? The starting point is [0,0], we can only move up and to the right. Thanks

    My solutions:
    $$ \binom{50}{20} - \binom{10}{5}\binom{40}{15} - \binom{25}{10}\binom{25}{10} -\binom{25}{15}\binom{25}{5}-\binom{40}{17}\binom{10}{3}$$
     
  2. jcsd
  3. Feb 1, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I moved the thread to the homework forum.

    You are subtracting some paths more than once, e. g. every path that passes both through [5,5] and [15,10]. One [15,10] should be [10,15] I guess?
     
  4. Feb 1, 2016 #3
    Yes, I use the principle of inclusion and exclusion
     
  5. Feb 1, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    So where do you consider the double-counting I mentioned?
     
  6. Feb 1, 2016 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You have included [15,10] twice in your list of forbidden points. What did you really mean?
     
  7. Feb 1, 2016 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The principle of inclusion and exclusion leads to expressions with both plus and minus signs, usually alternating. This is because you subtract out all the cases ruled out by each single criterion, then add back all that you have subtracted twice over because they were ruled out by two criteria, then add back in all that you've added back in too often because they were ruled out by three criteria, and so on.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatoric problem
  1. Combinatorics problem (Replies: 3)

  2. Combinatorics Problem (Replies: 3)

  3. Combinatorics problem (Replies: 2)

Loading...