The Knights Quest round table
up vote
0
down vote
favorite
pg. 20 of The Art of Enumerative Combinatorics, George E. Martin.
How many ways are there to select 4 knights from 15 knights sitting at a round table if no adjacent knights can be chosen?
On the next page he generalizes the problem to the following:
Suppose there are k knights and that q are to be chosen for the quest with no adjacent knights chosen. If we calculate the number of quests that have Lancelot as a member and multiply this number by k, then this product equals q times the number that we are seeking.
I don't understand why this last statement is true. I understand how to get the number of quests with lucky Lancelot as a member
${k-q-1} choose{q-1}$ but why should this number multiplied by k equal q times the total number of quests? I do not know how to visualize the second part of the problem.
combinatorics discrete-mathematics
asked 12 hours ago
Jason Butler
62
add a comment |
up vote
0
down vote
favorite
pg. 20 of The Art of Enumerative Combinatorics, George E. Martin.
How many ways are there to select 4 knights from 15 knights sitting at a round table if no adjacent knights can be chosen?
On the next page he generalizes the problem to the following:
Suppose there are k knights and that q are to be chosen for the quest with no adjacent knights chosen. If we calculate the number of quests that have Lancelot as a member and multiply this number by k, then this product equals q times the number that we are seeking.
I don't understand why this last statement is true. I understand how to get the number of quests with lucky Lancelot as a member
${k-q-1} choose{q-1}$ but why should this number multiplied by k equal q times the total number of quests? I do not know how to visualize the second part of the problem.
combinatorics discrete-mathematics
asked 12 hours ago
Jason Butler
62
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
pg. 20 of The Art of Enumerative Combinatorics, George E. Martin.
How many ways are there to select 4 knights from 15 knights sitting at a round table if no adjacent knights can be chosen?
On the next page he generalizes the problem to the following:
Suppose there are k knights and that q are to be chosen for the quest with no adjacent knights chosen. If we calculate the number of quests that have Lancelot as a member and multiply this number by k, then this product equals q times the number that we are seeking.
I don't understand why this last statement is true. I understand how to get the number of quests with lucky Lancelot as a member
${k-q-1} choose{q-1}$ but why should this number multiplied by k equal q times the total number of quests? I do not know how to visualize the second part of the problem.
combinatorics discrete-mathematics
asked 12 hours ago
Jason Butler
62
pg. 20 of The Art of Enumerative Combinatorics, George E. Martin.
How many ways are there to select 4 knights from 15 knights sitting at a round table if no adjacent knights can be chosen?
On the next page he generalizes the problem to the following:
Suppose there are k knights and that q are to be chosen for the quest with no adjacent knights chosen. If we calculate the number of quests that have Lancelot as a member and multiply this number by k, then this product equals q times the number that we are seeking.
I don't understand why this last statement is true. I understand how to get the number of quests with lucky Lancelot as a member
${k-q-1} choose{q-1}$ but why should this number multiplied by k equal q times the total number of quests? I do not know how to visualize the second part of the problem.
combinatorics discrete-mathematics
combinatorics discrete-mathematics
asked 12 hours ago
Jason Butler
62
asked 12 hours ago
Jason Butler
62
asked 12 hours ago
Jason Butler
62
asked 12 hours ago
Jason Butler
62
asked 12 hours ago
Jason Butler
62
62
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago
add a comment |
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 choose q-1}$. On each quest there are $q$ knights, so there are $frac kq{k-q-1 choose q-1}$ quests.
answered 11 hours ago
Ross Millikan
286k23195363
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
Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 choose q-1}$. On each quest there are $q$ knights, so there are $frac kq{k-q-1 choose q-1}$ quests.
answered 11 hours ago
Ross Millikan
286k23195363
add a comment |
up vote
0
down vote
Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 choose q-1}$. On each quest there are $q$ knights, so there are $frac kq{k-q-1 choose q-1}$ quests.
answered 11 hours ago
Ross Millikan
286k23195363
add a comment |
up vote
0
down vote
up vote
0
down vote
Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 choose q-1}$. On each quest there are $q$ knights, so there are $frac kq{k-q-1 choose q-1}$ quests.
answered 11 hours ago
Ross Millikan
286k23195363
Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 choose q-1}$. On each quest there are $q$ knights, so there are $frac kq{k-q-1 choose q-1}$ quests.
answered 11 hours ago
Ross Millikan
286k23195363
answered 11 hours ago
Ross Millikan
286k23195363
answered 11 hours ago
Ross Millikan
286k23195363
answered 11 hours ago
Ross Millikan
286k23195363
286k23195363
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%2f2995402%2fthe-knights-quest-round-table%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
You should be dividing by $q$ for the number of quests.
– Ross Millikan
11 hours ago