Mixing
Combinatorics problem in walking left and right
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
In this game, there will be $n$ turns. For the sake of clarity, let us say $n = 4$.
We have three options in this game: we can either stay in place ($O$), we can step to the left ($L$), or we can step to the right ($R$). However, the ability to step left only occurs on the the odd numbered turns, and the ability to step right only occurs on the even numbered turns. You may always choose to stay in place.
The goal of the game is to end up where you started. For example, this will work: $OOOO$, which represents always staying in place for each of the $n =4$ turns.
This will also work $LRLR$, as you will end up where you started with. Other examples are $ORLO$.
Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns.
Is there a way to find out (a) how many ways there are to do this?, (b) what is the distribution of these ways, labelled by the number of $L$ steps in total?
Observations:
- There must be the same number of $L$'s and $R$'s in your sequence.
- For $n$ odd, there must be an odd number of $O$'s.
- For $n$ even, there must be an even number of $O$'s.
Does anyone have any ideas? Is this a game anyone has played anywhere else before?
combinatorics
asked Jul 26 at 22:39
K L
161
add a comment |Â
up vote
1
down vote
favorite
In this game, there will be $n$ turns. For the sake of clarity, let us say $n = 4$.
We have three options in this game: we can either stay in place ($O$), we can step to the left ($L$), or we can step to the right ($R$). However, the ability to step left only occurs on the the odd numbered turns, and the ability to step right only occurs on the even numbered turns. You may always choose to stay in place.
The goal of the game is to end up where you started. For example, this will work: $OOOO$, which represents always staying in place for each of the $n =4$ turns.
This will also work $LRLR$, as you will end up where you started with. Other examples are $ORLO$.
Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns.
Is there a way to find out (a) how many ways there are to do this?, (b) what is the distribution of these ways, labelled by the number of $L$ steps in total?
Observations:
- There must be the same number of $L$'s and $R$'s in your sequence.
- For $n$ odd, there must be an odd number of $O$'s.
- For $n$ even, there must be an even number of $O$'s.
Does anyone have any ideas? Is this a game anyone has played anywhere else before?
combinatorics
asked Jul 26 at 22:39
K L
161
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
In this game, there will be $n$ turns. For the sake of clarity, let us say $n = 4$.
We have three options in this game: we can either stay in place ($O$), we can step to the left ($L$), or we can step to the right ($R$). However, the ability to step left only occurs on the the odd numbered turns, and the ability to step right only occurs on the even numbered turns. You may always choose to stay in place.
The goal of the game is to end up where you started. For example, this will work: $OOOO$, which represents always staying in place for each of the $n =4$ turns.
This will also work $LRLR$, as you will end up where you started with. Other examples are $ORLO$.
Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns.
Is there a way to find out (a) how many ways there are to do this?, (b) what is the distribution of these ways, labelled by the number of $L$ steps in total?
Observations:
- There must be the same number of $L$'s and $R$'s in your sequence.
- For $n$ odd, there must be an odd number of $O$'s.
- For $n$ even, there must be an even number of $O$'s.
Does anyone have any ideas? Is this a game anyone has played anywhere else before?
combinatorics
asked Jul 26 at 22:39
K L
161
In this game, there will be $n$ turns. For the sake of clarity, let us say $n = 4$.
We have three options in this game: we can either stay in place ($O$), we can step to the left ($L$), or we can step to the right ($R$). However, the ability to step left only occurs on the the odd numbered turns, and the ability to step right only occurs on the even numbered turns. You may always choose to stay in place.
The goal of the game is to end up where you started. For example, this will work: $OOOO$, which represents always staying in place for each of the $n =4$ turns.
This will also work $LRLR$, as you will end up where you started with. Other examples are $ORLO$.
Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns.
Is there a way to find out (a) how many ways there are to do this?, (b) what is the distribution of these ways, labelled by the number of $L$ steps in total?
Observations:
- There must be the same number of $L$'s and $R$'s in your sequence.
- For $n$ odd, there must be an odd number of $O$'s.
- For $n$ even, there must be an even number of $O$'s.
Does anyone have any ideas? Is this a game anyone has played anywhere else before?
combinatorics
asked Jul 26 at 22:39
K L
161
asked Jul 26 at 22:39
K L
161
asked Jul 26 at 22:39
K L
161
asked Jul 26 at 22:39
K L
161
161
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45
add a comment |Â
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $frac n2$ odd turns where you might move left. If you move left $k$ times, there are $n/2 choose k$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get
$$sum_k=0^n/2n/2 choose k^2$$
Alpha tells me this is $$n choose n/2$$
and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.
answered Jul 26 at 22:50
Ross Millikan
275k21186351
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
add a comment |Â
up vote
0
down vote
The number of ways is $binomnlfloor n/2 rfloor$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $lfloor n/2rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $lfloor n/2rfloor$ of their turns and command them to do the opposite action on each selected turn.
You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $ell$ left steps is
$$
binomlceil n/2 rceilellbinomlfloor n/2 rfloorell
$$
Dividing by the total number of ways, $binomnlfloor n/2 rfloor$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
add a comment |Â
up vote
0
down vote
The count of sequences is the count of ways to select $k$ from $lfloor n/2rfloor$ places for R and to select $k$ from $lceil n/2rceil$ places for L, for every $k$ that is an integer in $0,..,lfloor n/2rfloor$.
$$X_n~=sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorkdbinomlceil n/2rceilk\ =sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorlfloor n/2rfloor-kdbinomlceil n/2rceilk\=binomnlfloor n/2rfloor$$
(since $lfloor n/2rfloor+lceil n/2rceil=n$)
Vandemonde's Identity: for any positive integers $p,q,r$: $$sum_k=0^r dbinom pkdbinom qr-k=dbinomp+qr$$
answered Jul 26 at 23:10
Graham Kemp
80k43275
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $frac n2$ odd turns where you might move left. If you move left $k$ times, there are $n/2 choose k$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get
$$sum_k=0^n/2n/2 choose k^2$$
Alpha tells me this is $$n choose n/2$$
and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.
answered Jul 26 at 22:50
Ross Millikan
275k21186351
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
add a comment |Â
up vote
1
down vote
I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $frac n2$ odd turns where you might move left. If you move left $k$ times, there are $n/2 choose k$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get
$$sum_k=0^n/2n/2 choose k^2$$
Alpha tells me this is $$n choose n/2$$
and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.
answered Jul 26 at 22:50
Ross Millikan
275k21186351
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $frac n2$ odd turns where you might move left. If you move left $k$ times, there are $n/2 choose k$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get
$$sum_k=0^n/2n/2 choose k^2$$
Alpha tells me this is $$n choose n/2$$
and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.
answered Jul 26 at 22:50
Ross Millikan
275k21186351
I am assuming $n$ is even in the below.
You need the same number of $L$ moves as $R$ moves. There are $frac n2$ odd turns where you might move left. If you move left $k$ times, there are $n/2 choose k$ ways to choose the moves for left and similarly for the ways to choose the moves for right, so the total number of ways to wind up at the beginning is to sum over $k$ and get
$$sum_k=0^n/2n/2 choose k^2$$
Alpha tells me this is $$n choose n/2$$
and there is a neat combinatorial proof. Choose $n/2$ of the $n$ moves. For all the chosen moves make an $L$ for odd moves and an $O$ for even moves. For the non-chosen moves make an $O$ for odd moves and an $R$ for even moves. We have a bijection between the selections of $n/2$ and the strings that return you to the origin because the number of selected odd moves matches the number of non-selected even moves.
answered Jul 26 at 22:50
Ross Millikan
275k21186351
edited Jul 26 at 23:11
answered Jul 26 at 22:50
Ross Millikan
275k21186351
answered Jul 26 at 22:50
Ross Millikan
275k21186351
answered Jul 26 at 22:50
Ross Millikan
275k21186351
275k21186351
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
add a comment |Â
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
I've numerically verified your answer as correct, but I'm interested to see where my approach went wrong. The problem can be rephrased as the number of solutions to $$sum_k=1^n c_k(-1)^k = 0$$ with $c_k = 0, 1$ (where $c_k = 0$ means $O$ and $c_k = 1$ means $L$ or $R$). Or in other words, the number of polynomials with degree $n$ that have only coefficients in $0, 1$ and a root at $x = -1$. So we can factor the polynomial as $(x + 1)p(x)$ and see that $p(x)$ has degree $n-1$, is unrestricted over choice $0, 1$ except it may not have two consecutive $1$ coefficients.
– orlp
Jul 26 at 23:04
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
However this leads to the Fibonacci numbers, not the correct oeis.org/A001405.
– orlp
Jul 26 at 23:05
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
It is not obvious to me what restrictions there are on the coefficients of $p(x)$. I assume your prohibition of to consecutive $1$s is to avoid a coefficient $2$ when multiplying by $x+1$. Note that I assumed $n$ is even.
– Ross Millikan
Jul 26 at 23:11
add a comment |Â
up vote
0
down vote
The number of ways is $binomnlfloor n/2 rfloor$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $lfloor n/2rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $lfloor n/2rfloor$ of their turns and command them to do the opposite action on each selected turn.
You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $ell$ left steps is
$$
binomlceil n/2 rceilellbinomlfloor n/2 rfloorell
$$
Dividing by the total number of ways, $binomnlfloor n/2 rfloor$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
add a comment |Â
up vote
0
down vote
The number of ways is $binomnlfloor n/2 rfloor$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $lfloor n/2rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $lfloor n/2rfloor$ of their turns and command them to do the opposite action on each selected turn.
You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $ell$ left steps is
$$
binomlceil n/2 rceilellbinomlfloor n/2 rfloorell
$$
Dividing by the total number of ways, $binomnlfloor n/2 rfloor$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The number of ways is $binomnlfloor n/2 rfloor$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $lfloor n/2rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $lfloor n/2rfloor$ of their turns and command them to do the opposite action on each selected turn.
You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $ell$ left steps is
$$
binomlceil n/2 rceilellbinomlfloor n/2 rfloorell
$$
Dividing by the total number of ways, $binomnlfloor n/2 rfloor$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
The number of ways is $binomnlfloor n/2 rfloor$. Imagine a player that tries to move as far as possible to the right; on odd turns, they stay put, and on even turns, they move right. After $n$ turns, their position will be $lfloor n/2rfloor$. In order to change their behavior so that they end at the origin, you need to select exactly $lfloor n/2rfloor$ of their turns and command them to do the opposite action on each selected turn.
You asked about the distribution of the number of left steps as well. The number of ways to end up at the start having taken exactly $ell$ left steps is
$$
binomlceil n/2 rceilellbinomlfloor n/2 rfloorell
$$
Dividing by the total number of ways, $binomnlfloor n/2 rfloor$, the above defines a probability distribution known as the hypergeometric distribution. This arises when you have a population of $n$ people, $m$ of whom are considered special, and you sample $k$ of these people without replacement. The hypergeometric distribution governs the number of special people in your sample. This distribution is bell-shaped, and approaches a normal distribution as $n$ gets large.
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
answered Jul 27 at 1:12
Mike Earnest
14.9k11644
14.9k11644
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
add a comment |Â
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
Very clear and a great explanation! Thanks Mike!
– K L
Jul 27 at 16:57
add a comment |Â
up vote
0
down vote
The count of sequences is the count of ways to select $k$ from $lfloor n/2rfloor$ places for R and to select $k$ from $lceil n/2rceil$ places for L, for every $k$ that is an integer in $0,..,lfloor n/2rfloor$.
$$X_n~=sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorkdbinomlceil n/2rceilk\ =sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorlfloor n/2rfloor-kdbinomlceil n/2rceilk\=binomnlfloor n/2rfloor$$
(since $lfloor n/2rfloor+lceil n/2rceil=n$)
Vandemonde's Identity: for any positive integers $p,q,r$: $$sum_k=0^r dbinom pkdbinom qr-k=dbinomp+qr$$
answered Jul 26 at 23:10
Graham Kemp
80k43275
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
add a comment |Â
up vote
0
down vote
The count of sequences is the count of ways to select $k$ from $lfloor n/2rfloor$ places for R and to select $k$ from $lceil n/2rceil$ places for L, for every $k$ that is an integer in $0,..,lfloor n/2rfloor$.
$$X_n~=sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorkdbinomlceil n/2rceilk\ =sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorlfloor n/2rfloor-kdbinomlceil n/2rceilk\=binomnlfloor n/2rfloor$$
(since $lfloor n/2rfloor+lceil n/2rceil=n$)
Vandemonde's Identity: for any positive integers $p,q,r$: $$sum_k=0^r dbinom pkdbinom qr-k=dbinomp+qr$$
answered Jul 26 at 23:10
Graham Kemp
80k43275
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The count of sequences is the count of ways to select $k$ from $lfloor n/2rfloor$ places for R and to select $k$ from $lceil n/2rceil$ places for L, for every $k$ that is an integer in $0,..,lfloor n/2rfloor$.
$$X_n~=sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorkdbinomlceil n/2rceilk\ =sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorlfloor n/2rfloor-kdbinomlceil n/2rceilk\=binomnlfloor n/2rfloor$$
(since $lfloor n/2rfloor+lceil n/2rceil=n$)
Vandemonde's Identity: for any positive integers $p,q,r$: $$sum_k=0^r dbinom pkdbinom qr-k=dbinomp+qr$$
answered Jul 26 at 23:10
Graham Kemp
80k43275
The count of sequences is the count of ways to select $k$ from $lfloor n/2rfloor$ places for R and to select $k$ from $lceil n/2rceil$ places for L, for every $k$ that is an integer in $0,..,lfloor n/2rfloor$.
$$X_n~=sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorkdbinomlceil n/2rceilk\ =sum_k=0^lfloor n/2rfloordbinom lfloor n/2rfloorlfloor n/2rfloor-kdbinomlceil n/2rceilk\=binomnlfloor n/2rfloor$$
(since $lfloor n/2rfloor+lceil n/2rceil=n$)
Vandemonde's Identity: for any positive integers $p,q,r$: $$sum_k=0^r dbinom pkdbinom qr-k=dbinomp+qr$$
answered Jul 26 at 23:10
Graham Kemp
80k43275
edited Jul 27 at 2:05
answered Jul 26 at 23:10
Graham Kemp
80k43275
answered Jul 26 at 23:10
Graham Kemp
80k43275
answered Jul 26 at 23:10
Graham Kemp
80k43275
80k43275
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
add a comment |Â
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
I think your floor and ceiling are backwards in the first line. If $n$ is odd there is an extra chance for an $L$. Good for you for handling odd $n$
– Ross Millikan
Jul 26 at 23:13
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
Doesn't Vandemonde also imply $X_2m+1=binom2m+1m$?
– Mike Earnest
Jul 27 at 0:53
1
1
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
$...tinytextYes$
– Graham Kemp
Jul 27 at 1:57
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
Great explanation, but one question: Is the upper limit of the summation the floor of $n/2$ or the ceiling? I am inclined to think the ceiling.
– K L
Jul 27 at 16:58
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
It can't be the ceiling. The upper bound is the maximum number both of left steps and of right steps, the sum of which maynot exceed the number of turns. @KL
– Graham Kemp
Jul 27 at 22:00
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863885%2fcombinatorics-problem-in-walking-left-and-right%23new-answer', 'question_page');
);
Post as a guest
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
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
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
"Note that $RLRL$ does not work, since you cannot step right on the odd numbered turns and you cannot step left on the even numbered turns." Can you be more clear? Is $RLRL$ not just an invalid string, rather than one that "doesn't work". Because one might also argue that it does work, as $R/L$ could "do nothing" when used on the wrong turn - leaving you in the same place.
– orlp
Jul 26 at 22:45