How many different operations can be defined in a finite groupoid with a given property?
up vote
4
down vote
favorite
Set $B=left{ 1, 2, ... 18 right}$ is given. How many different operations $*$ can be defined so that $(B,*)$ is a groupoid with a property that $|left{i|i*(19-i) neq i ∧ i*(19-i) neq (19-i)right}| = k$, where $k in B∪left{ 0 right}$.
What exactly is $k$ here? The solution is given as:
$binom{18}{k}(18-2)^k2^{18-k}18^{18^2-18}$.
I understand that the part within the parentheses say that eg. $18*1 neq 1 ∧ neq 18$ which explains the $18^{18^2-18}$
as a diagonal which follows these rules does not have 18 possibilities anymore. But what does this $k$ mean? And how does it change the result?
combinatorics elementary-set-theory magma
add a comment |
up vote
4
down vote
favorite
Set $B=left{ 1, 2, ... 18 right}$ is given. How many different operations $*$ can be defined so that $(B,*)$ is a groupoid with a property that $|left{i|i*(19-i) neq i ∧ i*(19-i) neq (19-i)right}| = k$, where $k in B∪left{ 0 right}$.
What exactly is $k$ here? The solution is given as:
$binom{18}{k}(18-2)^k2^{18-k}18^{18^2-18}$.
I understand that the part within the parentheses say that eg. $18*1 neq 1 ∧ neq 18$ which explains the $18^{18^2-18}$
as a diagonal which follows these rules does not have 18 possibilities anymore. But what does this $k$ mean? And how does it change the result?
combinatorics elementary-set-theory magma
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Set $B=left{ 1, 2, ... 18 right}$ is given. How many different operations $*$ can be defined so that $(B,*)$ is a groupoid with a property that $|left{i|i*(19-i) neq i ∧ i*(19-i) neq (19-i)right}| = k$, where $k in B∪left{ 0 right}$.
What exactly is $k$ here? The solution is given as:
$binom{18}{k}(18-2)^k2^{18-k}18^{18^2-18}$.
I understand that the part within the parentheses say that eg. $18*1 neq 1 ∧ neq 18$ which explains the $18^{18^2-18}$
as a diagonal which follows these rules does not have 18 possibilities anymore. But what does this $k$ mean? And how does it change the result?
combinatorics elementary-set-theory magma
Set $B=left{ 1, 2, ... 18 right}$ is given. How many different operations $*$ can be defined so that $(B,*)$ is a groupoid with a property that $|left{i|i*(19-i) neq i ∧ i*(19-i) neq (19-i)right}| = k$, where $k in B∪left{ 0 right}$.
What exactly is $k$ here? The solution is given as:
$binom{18}{k}(18-2)^k2^{18-k}18^{18^2-18}$.
I understand that the part within the parentheses say that eg. $18*1 neq 1 ∧ neq 18$ which explains the $18^{18^2-18}$
as a diagonal which follows these rules does not have 18 possibilities anymore. But what does this $k$ mean? And how does it change the result?
combinatorics elementary-set-theory magma
combinatorics elementary-set-theory magma
edited Nov 21 at 14:39
Arnaud D.
15.6k52343
15.6k52343
asked Jun 20 at 20:02
edward_d
1601211
1601211
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
$k$ is the cardinality of the set of elements $i$ such that $i*(19-i)notin{i,19-i}$; that is, it is the number of such elements.
Without constraints, there would be $18^{18^2}$ different operations, as we can independently assign one of $18$ results of the operation to each of the $18^2$ pairs of operands. Given the constraint on the cardinality of the set, we can choose the $k$ elements in the set in $binom{18}k$ ways, assign one of $18-2$ admissible results to their products of the form $i*(19-i)$, yielding a factor $(18-2)^k$, and for the remaining $18-k$ elements we have to assign one of the two inadmissible results $i$ and $19-i$ to their products of the form $i*(19-i)$, yielding a factor $2^{18-k}$. That leaves $18^2-18$ products to be freely chosen among the $18$ possibilities, yielding a factor $18^{18^2-18}$.
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
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%2f2826513%2fhow-many-different-operations-can-be-defined-in-a-finite-groupoid-with-a-given-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
$k$ is the cardinality of the set of elements $i$ such that $i*(19-i)notin{i,19-i}$; that is, it is the number of such elements.
Without constraints, there would be $18^{18^2}$ different operations, as we can independently assign one of $18$ results of the operation to each of the $18^2$ pairs of operands. Given the constraint on the cardinality of the set, we can choose the $k$ elements in the set in $binom{18}k$ ways, assign one of $18-2$ admissible results to their products of the form $i*(19-i)$, yielding a factor $(18-2)^k$, and for the remaining $18-k$ elements we have to assign one of the two inadmissible results $i$ and $19-i$ to their products of the form $i*(19-i)$, yielding a factor $2^{18-k}$. That leaves $18^2-18$ products to be freely chosen among the $18$ possibilities, yielding a factor $18^{18^2-18}$.
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
add a comment |
up vote
1
down vote
accepted
$k$ is the cardinality of the set of elements $i$ such that $i*(19-i)notin{i,19-i}$; that is, it is the number of such elements.
Without constraints, there would be $18^{18^2}$ different operations, as we can independently assign one of $18$ results of the operation to each of the $18^2$ pairs of operands. Given the constraint on the cardinality of the set, we can choose the $k$ elements in the set in $binom{18}k$ ways, assign one of $18-2$ admissible results to their products of the form $i*(19-i)$, yielding a factor $(18-2)^k$, and for the remaining $18-k$ elements we have to assign one of the two inadmissible results $i$ and $19-i$ to their products of the form $i*(19-i)$, yielding a factor $2^{18-k}$. That leaves $18^2-18$ products to be freely chosen among the $18$ possibilities, yielding a factor $18^{18^2-18}$.
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
$k$ is the cardinality of the set of elements $i$ such that $i*(19-i)notin{i,19-i}$; that is, it is the number of such elements.
Without constraints, there would be $18^{18^2}$ different operations, as we can independently assign one of $18$ results of the operation to each of the $18^2$ pairs of operands. Given the constraint on the cardinality of the set, we can choose the $k$ elements in the set in $binom{18}k$ ways, assign one of $18-2$ admissible results to their products of the form $i*(19-i)$, yielding a factor $(18-2)^k$, and for the remaining $18-k$ elements we have to assign one of the two inadmissible results $i$ and $19-i$ to their products of the form $i*(19-i)$, yielding a factor $2^{18-k}$. That leaves $18^2-18$ products to be freely chosen among the $18$ possibilities, yielding a factor $18^{18^2-18}$.
$k$ is the cardinality of the set of elements $i$ such that $i*(19-i)notin{i,19-i}$; that is, it is the number of such elements.
Without constraints, there would be $18^{18^2}$ different operations, as we can independently assign one of $18$ results of the operation to each of the $18^2$ pairs of operands. Given the constraint on the cardinality of the set, we can choose the $k$ elements in the set in $binom{18}k$ ways, assign one of $18-2$ admissible results to their products of the form $i*(19-i)$, yielding a factor $(18-2)^k$, and for the remaining $18-k$ elements we have to assign one of the two inadmissible results $i$ and $19-i$ to their products of the form $i*(19-i)$, yielding a factor $2^{18-k}$. That leaves $18^2-18$ products to be freely chosen among the $18$ possibilities, yielding a factor $18^{18^2-18}$.
edited Jun 20 at 21:28
answered Jun 20 at 20:42
joriki
170k10183342
170k10183342
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
add a comment |
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
Did you mean 18 over k ways to choose k and not 18 over 2?
– edward_d
Jun 20 at 20:52
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
@edward_d: I did, thanks; I fixed it.
– joriki
Jun 20 at 21:28
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f2826513%2fhow-many-different-operations-can-be-defined-in-a-finite-groupoid-with-a-given-p%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