## A Path Counting Problem

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
jwroblewski44
Posts: 13
Joined: Mon Jun 03, 2013 1:49 am
Contact:

### A Path Counting Problem

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!

Posts: 136
Joined: Sun Feb 22, 2009 11:12 pm

### Re: A Path Counting Problem

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.

jwroblewski44
Posts: 13
Joined: Mon Jun 03, 2013 1:49 am
Contact:

### Re: A Path Counting Problem

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.