Count sequences of length $n$, with fixed first and last element and elements differ by one
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'm trying to solve the following problem: given $n, x, y$, count sequences of length $n$ with fixed first element - $x$ and last one - $y$, such that any two adjacent elements differ by one or minus one.
For example $n=3, x = 1, y = 1$, the answer is $2$, because there are two sequences of length $3$ which should be counted $[ 1,0,1], [1, 2,1]$.
I came up with function $f(i, x)$ which means sequences of length $i$ with $i-th$ element being $x$. We can express $f(i, x) = f(i-1, x-1) + f(i-1, x+1)$.
But this is hard to compute for large numbers, is there any solution that can solve this with combinatorics.
sequences-and-series combinatorics
asked Aug 13 at 11:15
someone123123
367213
add a comment |Â
up vote
1
down vote
favorite
I'm trying to solve the following problem: given $n, x, y$, count sequences of length $n$ with fixed first element - $x$ and last one - $y$, such that any two adjacent elements differ by one or minus one.
For example $n=3, x = 1, y = 1$, the answer is $2$, because there are two sequences of length $3$ which should be counted $[ 1,0,1], [1, 2,1]$.
I came up with function $f(i, x)$ which means sequences of length $i$ with $i-th$ element being $x$. We can express $f(i, x) = f(i-1, x-1) + f(i-1, x+1)$.
But this is hard to compute for large numbers, is there any solution that can solve this with combinatorics.
sequences-and-series combinatorics
asked Aug 13 at 11:15
someone123123
367213
2
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm trying to solve the following problem: given $n, x, y$, count sequences of length $n$ with fixed first element - $x$ and last one - $y$, such that any two adjacent elements differ by one or minus one.
For example $n=3, x = 1, y = 1$, the answer is $2$, because there are two sequences of length $3$ which should be counted $[ 1,0,1], [1, 2,1]$.
I came up with function $f(i, x)$ which means sequences of length $i$ with $i-th$ element being $x$. We can express $f(i, x) = f(i-1, x-1) + f(i-1, x+1)$.
But this is hard to compute for large numbers, is there any solution that can solve this with combinatorics.
sequences-and-series combinatorics
asked Aug 13 at 11:15
someone123123
367213
I'm trying to solve the following problem: given $n, x, y$, count sequences of length $n$ with fixed first element - $x$ and last one - $y$, such that any two adjacent elements differ by one or minus one.
For example $n=3, x = 1, y = 1$, the answer is $2$, because there are two sequences of length $3$ which should be counted $[ 1,0,1], [1, 2,1]$.
I came up with function $f(i, x)$ which means sequences of length $i$ with $i-th$ element being $x$. We can express $f(i, x) = f(i-1, x-1) + f(i-1, x+1)$.
But this is hard to compute for large numbers, is there any solution that can solve this with combinatorics.
sequences-and-series combinatorics
asked Aug 13 at 11:15
someone123123
367213
asked Aug 13 at 11:15
someone123123
367213
asked Aug 13 at 11:15
someone123123
367213
asked Aug 13 at 11:15
someone123123
367213
367213
2
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21
add a comment |Â
2
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21
2
2
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.
answered Aug 13 at 16:05
Munchhausen
68615
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.
answered Aug 13 at 16:05
Munchhausen
68615
add a comment |Â
up vote
2
down vote
accepted
We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.
answered Aug 13 at 16:05
Munchhausen
68615
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.
answered Aug 13 at 16:05
Munchhausen
68615
We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.
answered Aug 13 at 16:05
Munchhausen
68615
answered Aug 13 at 16:05
Munchhausen
68615
answered Aug 13 at 16:05
Munchhausen
68615
answered Aug 13 at 16:05
Munchhausen
68615
68615
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2881260%2fcount-sequences-of-length-n-with-fixed-first-and-last-element-and-elements-di%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
2
Hint: any such sequence can be described as a sequence of $pm 1's$ of length $n-1$ where we can compute in advance the number of $+1's$ and $-1's$. In your case, for example, we know there has to be exactly one of each.
– lulu
Aug 13 at 11:21