A Path Counting Problem

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

A Path Counting Problem

Postby jwroblewski44 on Tue May 06, 2014 9:39 pm

I am working on this problem: https://projecteuler.net/problem=15

I have a feeling that I need to be looking at combinatorics, specifically "choosing". I've also looked at Pascal's triangle but I still don't know how I would apply this to the problem.

Any help without giving me the answer directly would be much appreciated. Thanks!
jwroblewski44
 
Posts: 13
Joined: Mon Jun 03, 2013 1:49 am

Sponsor

Sponsor
 

Re: A Path Counting Problem

Postby theshadow on Wed May 07, 2014 1:28 pm

jwroblewski44 wrote:I am working on this problem: https://projecteuler.net/problem=15

I have a feeling that I need to be looking at combinatorics, specifically "choosing". I've also looked at Pascal's triangle but I still don't know how I would apply this to the problem.

Try to figure out a formula for getting "6" for the example they give you. Think about how many steps you'll have to take, no matter what way you go. Since you only go down or right, how many choices do you have for each step? If you write this like you do for "heads" and "tails" (but with D and R instead of H and T), what letter strings can you get? How many of those strings can you get? They probably explain it better here.
theshadow
 
Posts: 82
Joined: Sun Feb 22, 2009 11:12 pm

Re: A Path Counting Problem

Postby jwroblewski44 on Thu May 08, 2014 5:29 pm

Thank you for the help.

I'll try working on a formula that accounts for every option a particular node has and every possible combination. It seems as though you can't just count the number of nodes as assume that each node can make a right or down move because nodes on the far right row obviously cannot move right, and same respectively for the bottom row.

I'll post back if I have any other questions.
jwroblewski44
 
Posts: 13
Joined: Mon Jun 03, 2013 1:49 am


Return to Discrete Math