How many ways to reach point?
up vote
0
down vote
favorite
You're sitting at coordinates (0,0) and have 3 options:
- Go up diagonally eg:
(0,0) -> (1,1)
- Go straight 1 step eg:
(0,0) -> (1,0)
- Go down diagonally eg:
(2,2) -> (3,1)
You want to reach (p,0) and you're not allowed to go under 0 (Eg, you can only walk on >= 0 coordinates) and you can only go up to a point h, in height.
How many ways can you reach the point (p, 0) from (0,0) given to constraints mentioned above ?
combinatorics
asked Nov 14 at 15:29
Erik Cristian Seulean
385
|
show 16 more comments
up vote
0
down vote
favorite
You're sitting at coordinates (0,0) and have 3 options:
- Go up diagonally eg:
(0,0) -> (1,1)
- Go straight 1 step eg:
(0,0) -> (1,0)
- Go down diagonally eg:
(2,2) -> (3,1)
You want to reach (p,0) and you're not allowed to go under 0 (Eg, you can only walk on >= 0 coordinates) and you can only go up to a point h, in height.
How many ways can you reach the point (p, 0) from (0,0) given to constraints mentioned above ?
combinatorics
asked Nov 14 at 15:29
Erik Cristian Seulean
385
2
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
1
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45
|
show 16 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
You're sitting at coordinates (0,0) and have 3 options:
- Go up diagonally eg:
(0,0) -> (1,1)
- Go straight 1 step eg:
(0,0) -> (1,0)
- Go down diagonally eg:
(2,2) -> (3,1)
You want to reach (p,0) and you're not allowed to go under 0 (Eg, you can only walk on >= 0 coordinates) and you can only go up to a point h, in height.
How many ways can you reach the point (p, 0) from (0,0) given to constraints mentioned above ?
combinatorics
asked Nov 14 at 15:29
Erik Cristian Seulean
385
You're sitting at coordinates (0,0) and have 3 options:
- Go up diagonally eg:
(0,0) -> (1,1)
- Go straight 1 step eg:
(0,0) -> (1,0)
- Go down diagonally eg:
(2,2) -> (3,1)
You want to reach (p,0) and you're not allowed to go under 0 (Eg, you can only walk on >= 0 coordinates) and you can only go up to a point h, in height.
How many ways can you reach the point (p, 0) from (0,0) given to constraints mentioned above ?
combinatorics
combinatorics
asked Nov 14 at 15:29
Erik Cristian Seulean
385
asked Nov 14 at 15:29
Erik Cristian Seulean
385
edited Nov 14 at 15:43
asked Nov 14 at 15:29
Erik Cristian Seulean
385
asked Nov 14 at 15:29
Erik Cristian Seulean
385
asked Nov 14 at 15:29
Erik Cristian Seulean
385
385
2
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
1
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45
|
show 16 more comments
2
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
1
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45
2
2
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
1
1
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45
|
show 16 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.
answered Nov 15 at 12:26
Peter Taylor
8,27912240
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.
answered Nov 15 at 12:26
Peter Taylor
8,27912240
add a comment |
up vote
0
down vote
accepted
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.
answered Nov 15 at 12:26
Peter Taylor
8,27912240
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.
answered Nov 15 at 12:26
Peter Taylor
8,27912240
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.
answered Nov 15 at 12:26
Peter Taylor
8,27912240
answered Nov 15 at 12:26
Peter Taylor
8,27912240
answered Nov 15 at 12:26
Peter Taylor
8,27912240
answered Nov 15 at 12:26
Peter Taylor
8,27912240
8,27912240
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998397%2fhow-many-ways-to-reach-point%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Infinitely many, since you can start at $(0,0)$ and go up to $(1,1)$ and back down to $(0,0)$ as often as you like.
– lulu
Nov 14 at 15:31
Not sure the rules are clear, by the way. Does move $2$ also allow $(0,0)mapsto (0,1)$ or can you only use $2$ to move up? And can you go from $(1,0)mapsto (0,0)$ or is move $2$ only one way? Also, did you mean to have some rule which excludes or restricts loops of the form I invoked?
– lulu
Nov 14 at 15:34
"You want to reach (p,0)" - What is p?
– NoChance
Nov 14 at 15:35
I didn't say you can walk backwards. Also, p is a random point, consider p being 100 if it makes it easier for you to think about it.
– Erik Cristian Seulean
Nov 14 at 15:37
1
So, every possible move increases the $x$ coordinate, yes? So all paths must have length $p$, yes?
– lulu
Nov 14 at 15:45