Combination Problem Part 1 about Catalan Number
up vote
1
down vote
favorite
Refer to an election in which two candidates Wright and Upshaw ran for dogcatcher. After each vote was tabulated, Wright was never behind Upshaw. This problem is known as the ballot problem.
Suppose that each candidate received exactly $r$ votes. Show that the number of ways the votes could be counted is $C_r$, the $r-$th Catalan number.
My issue with this is, what's the relation between Combinations and the Catalan number? I do have the answer, but I don't understand the logic behind the counting argument.
discrete-mathematics combinations catalan-numbers
edited Nov 13 at 7:26
AspiringMat
478518
asked Nov 13 at 7:02
Aly J
61
add a comment |
up vote
1
down vote
favorite
Refer to an election in which two candidates Wright and Upshaw ran for dogcatcher. After each vote was tabulated, Wright was never behind Upshaw. This problem is known as the ballot problem.
Suppose that each candidate received exactly $r$ votes. Show that the number of ways the votes could be counted is $C_r$, the $r-$th Catalan number.
My issue with this is, what's the relation between Combinations and the Catalan number? I do have the answer, but I don't understand the logic behind the counting argument.
discrete-mathematics combinations catalan-numbers
edited Nov 13 at 7:26
AspiringMat
478518
asked Nov 13 at 7:02
Aly J
61
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Refer to an election in which two candidates Wright and Upshaw ran for dogcatcher. After each vote was tabulated, Wright was never behind Upshaw. This problem is known as the ballot problem.
Suppose that each candidate received exactly $r$ votes. Show that the number of ways the votes could be counted is $C_r$, the $r-$th Catalan number.
My issue with this is, what's the relation between Combinations and the Catalan number? I do have the answer, but I don't understand the logic behind the counting argument.
discrete-mathematics combinations catalan-numbers
edited Nov 13 at 7:26
AspiringMat
478518
asked Nov 13 at 7:02
Aly J
61
Refer to an election in which two candidates Wright and Upshaw ran for dogcatcher. After each vote was tabulated, Wright was never behind Upshaw. This problem is known as the ballot problem.
Suppose that each candidate received exactly $r$ votes. Show that the number of ways the votes could be counted is $C_r$, the $r-$th Catalan number.
My issue with this is, what's the relation between Combinations and the Catalan number? I do have the answer, but I don't understand the logic behind the counting argument.
discrete-mathematics combinations catalan-numbers
discrete-mathematics combinations catalan-numbers
edited Nov 13 at 7:26
AspiringMat
478518
asked Nov 13 at 7:02
Aly J
61
edited Nov 13 at 7:26
AspiringMat
478518
asked Nov 13 at 7:02
Aly J
61
edited Nov 13 at 7:26
AspiringMat
478518
edited Nov 13 at 7:26
AspiringMat
478518
edited Nov 13 at 7:26
AspiringMat
478518
478518
asked Nov 13 at 7:02
Aly J
61
asked Nov 13 at 7:02
Aly J
61
asked Nov 13 at 7:02
Aly J
61
61
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2996421%2fcombination-problem-part-1-about-catalan-number%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
