Mixing
Number of sequences satisfying certain constraints
$begingroup$
I've got this problem from a contest training that was held today at my school, the competition is not ongoing, in fact I will provied here the link to the solutions: Problem's solutions
That being said, I felt the solution to one of the problems was kinda lame since it relied on you knowing the theory behind Catalan numbers, the problem is the following:
How many sequences are there, such that $a_ige 0 ,forall i $, $a_0=a_{18}=0$ and $a_i=a_{i-1}pm1$ $forall 1le ile 18$
My attempt:
I didn't get very far in this one, I drew a table with 19 blank spots, put a zero at the beginning, one at the end, and then tought I could just use simple permutations (Basically count the number of sequences just by counting the number of ways there are to put eight "+1's" and eight "-1's" and divide by the permutation of the repeated elements, so $frac{16!}{8!cdot 8!}$, then I remembered that $a_i ge 0$ for all $i$ condition, and got stuck, I tought I could maybe use engineer's induction (analyze small cases) but I decided to just move onto other problems, any insight on this one is much appreciated.
Also, the answer according to the solutions is the nineth catalan number, $C_9=frac{1}{10}{18 choose 9}=4862$
combinatorics contest-math
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
$endgroup$
add a comment |
$begingroup$
I've got this problem from a contest training that was held today at my school, the competition is not ongoing, in fact I will provied here the link to the solutions: Problem's solutions
That being said, I felt the solution to one of the problems was kinda lame since it relied on you knowing the theory behind Catalan numbers, the problem is the following:
How many sequences are there, such that $a_ige 0 ,forall i $, $a_0=a_{18}=0$ and $a_i=a_{i-1}pm1$ $forall 1le ile 18$
My attempt:
I didn't get very far in this one, I drew a table with 19 blank spots, put a zero at the beginning, one at the end, and then tought I could just use simple permutations (Basically count the number of sequences just by counting the number of ways there are to put eight "+1's" and eight "-1's" and divide by the permutation of the repeated elements, so $frac{16!}{8!cdot 8!}$, then I remembered that $a_i ge 0$ for all $i$ condition, and got stuck, I tought I could maybe use engineer's induction (analyze small cases) but I decided to just move onto other problems, any insight on this one is much appreciated.
Also, the answer according to the solutions is the nineth catalan number, $C_9=frac{1}{10}{18 choose 9}=4862$
combinatorics contest-math
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
$endgroup$
add a comment |
$begingroup$
I've got this problem from a contest training that was held today at my school, the competition is not ongoing, in fact I will provied here the link to the solutions: Problem's solutions
That being said, I felt the solution to one of the problems was kinda lame since it relied on you knowing the theory behind Catalan numbers, the problem is the following:
How many sequences are there, such that $a_ige 0 ,forall i $, $a_0=a_{18}=0$ and $a_i=a_{i-1}pm1$ $forall 1le ile 18$
My attempt:
I didn't get very far in this one, I drew a table with 19 blank spots, put a zero at the beginning, one at the end, and then tought I could just use simple permutations (Basically count the number of sequences just by counting the number of ways there are to put eight "+1's" and eight "-1's" and divide by the permutation of the repeated elements, so $frac{16!}{8!cdot 8!}$, then I remembered that $a_i ge 0$ for all $i$ condition, and got stuck, I tought I could maybe use engineer's induction (analyze small cases) but I decided to just move onto other problems, any insight on this one is much appreciated.
Also, the answer according to the solutions is the nineth catalan number, $C_9=frac{1}{10}{18 choose 9}=4862$
combinatorics contest-math
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
$endgroup$
I've got this problem from a contest training that was held today at my school, the competition is not ongoing, in fact I will provied here the link to the solutions: Problem's solutions
That being said, I felt the solution to one of the problems was kinda lame since it relied on you knowing the theory behind Catalan numbers, the problem is the following:
How many sequences are there, such that $a_ige 0 ,forall i $, $a_0=a_{18}=0$ and $a_i=a_{i-1}pm1$ $forall 1le ile 18$
My attempt:
I didn't get very far in this one, I drew a table with 19 blank spots, put a zero at the beginning, one at the end, and then tought I could just use simple permutations (Basically count the number of sequences just by counting the number of ways there are to put eight "+1's" and eight "-1's" and divide by the permutation of the repeated elements, so $frac{16!}{8!cdot 8!}$, then I remembered that $a_i ge 0$ for all $i$ condition, and got stuck, I tought I could maybe use engineer's induction (analyze small cases) but I decided to just move onto other problems, any insight on this one is much appreciated.
Also, the answer according to the solutions is the nineth catalan number, $C_9=frac{1}{10}{18 choose 9}=4862$
combinatorics contest-math
combinatorics contest-math
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
asked Jan 14 at 19:29
Spasoje DurovicSpasoje Durovic
36510
36510
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.
For each $1le ile 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+dots+d_{i}$. Each $d_i=pm1$. Now, consider the list of $19$ numbers
$$
(1,d_1,d_2,dots,d_{18})tag{$*$}
$$
Since each $b_ige 0$, each partial sum $1+d_1+dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+dots+d_{18}$ is equal to $1$.
How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.
Lemma: Let $(d_1,dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},dots,d_n,d_1,dots,d_{k})$.
Since there are $binom{19}{10}$ lists of $pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is
$$
frac1{19}binom{19}{10}=frac1{10}binom{18}9.
$$
I leave it to you to prove the Lemma.
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
$endgroup$
add a comment |
$begingroup$
Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_ileq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.
Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.
answered Jan 14 at 22:38
user574848user574848
414117
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3073630%2fnumber-of-sequences-satisfying-certain-constraints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.
For each $1le ile 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+dots+d_{i}$. Each $d_i=pm1$. Now, consider the list of $19$ numbers
$$
(1,d_1,d_2,dots,d_{18})tag{$*$}
$$
Since each $b_ige 0$, each partial sum $1+d_1+dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+dots+d_{18}$ is equal to $1$.
How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.
Lemma: Let $(d_1,dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},dots,d_n,d_1,dots,d_{k})$.
Since there are $binom{19}{10}$ lists of $pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is
$$
frac1{19}binom{19}{10}=frac1{10}binom{18}9.
$$
I leave it to you to prove the Lemma.
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
$endgroup$
add a comment |
$begingroup$
This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.
For each $1le ile 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+dots+d_{i}$. Each $d_i=pm1$. Now, consider the list of $19$ numbers
$$
(1,d_1,d_2,dots,d_{18})tag{$*$}
$$
Since each $b_ige 0$, each partial sum $1+d_1+dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+dots+d_{18}$ is equal to $1$.
How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.
Lemma: Let $(d_1,dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},dots,d_n,d_1,dots,d_{k})$.
Since there are $binom{19}{10}$ lists of $pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is
$$
frac1{19}binom{19}{10}=frac1{10}binom{18}9.
$$
I leave it to you to prove the Lemma.
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
$endgroup$
add a comment |
$begingroup$
This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.
For each $1le ile 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+dots+d_{i}$. Each $d_i=pm1$. Now, consider the list of $19$ numbers
$$
(1,d_1,d_2,dots,d_{18})tag{$*$}
$$
Since each $b_ige 0$, each partial sum $1+d_1+dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+dots+d_{18}$ is equal to $1$.
How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.
Lemma: Let $(d_1,dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},dots,d_n,d_1,dots,d_{k})$.
Since there are $binom{19}{10}$ lists of $pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is
$$
frac1{19}binom{19}{10}=frac1{10}binom{18}9.
$$
I leave it to you to prove the Lemma.
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
$endgroup$
This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.
For each $1le ile 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+dots+d_{i}$. Each $d_i=pm1$. Now, consider the list of $19$ numbers
$$
(1,d_1,d_2,dots,d_{18})tag{$*$}
$$
Since each $b_ige 0$, each partial sum $1+d_1+dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+dots+d_{18}$ is equal to $1$.
How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.
Lemma: Let $(d_1,dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},dots,d_n,d_1,dots,d_{k})$.
Since there are $binom{19}{10}$ lists of $pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is
$$
frac1{19}binom{19}{10}=frac1{10}binom{18}9.
$$
I leave it to you to prove the Lemma.
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
answered Jan 14 at 23:23
Mike EarnestMike Earnest
23.3k12051
23.3k12051
add a comment |
add a comment |
$begingroup$
Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_ileq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.
Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.
answered Jan 14 at 22:38
user574848user574848
414117
$endgroup$
add a comment |
$begingroup$
Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_ileq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.
Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.
answered Jan 14 at 22:38
user574848user574848
414117
$endgroup$
add a comment |
$begingroup$
Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_ileq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.
Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.
answered Jan 14 at 22:38
user574848user574848
414117
$endgroup$
Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_ileq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.
Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.
answered Jan 14 at 22:38
user574848user574848
414117
answered Jan 14 at 22:38
user574848user574848
414117
answered Jan 14 at 22:38
user574848user574848
414117
answered Jan 14 at 22:38
user574848user574848
414117
414117
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3073630%2fnumber-of-sequences-satisfying-certain-constraints%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
