How many equivalence relations on S have exactly 3 equivalence classes?How many equivalence relations $S$ on $A$ are there for which $R⊆S$ ($R$ is an equivalence relation on a set $A$, with $4$ equivalence classes)How many equivalence-relations does the class have?Homeomorphism are equivalence relations, so what are the equivalence classes?Describe equivalence classes from equivalence relationsHow to prove equivalence relationsHow many ways of having 2 Equivalence Classes with Magnitude 3Stirling numbers and equivalence classesNumber of classes an equivalence relation partitions a set XEquivalence relations S on A with R being a relation on A with 4 equivalence classes.Uncountably Many Equivalence Classes
What is a romance in Latin?
Do scales need to be in alphabetical order?
What reasons are there for a Capitalist to oppose a 100% inheritance tax?
How badly should I try to prevent a user from XSSing themselves?
Forgetting the musical notes while performing in concert
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
Why no variance term in Bayesian logistic regression?
How to prevent "they're falling in love" trope
Should I tell management that I intend to leave due to bad software development practices?
How do I deal with an unproductive colleague in a small company?
Probability that a draw from a normal distribution is some number greater than another draw from the same distribution
Expand and Contract
Detention in 1997
What killed these X2 caps?
How would I stat a creature to be immune to everything but the Magic Missile spell? (just for fun)
Is this a hacking script in function.php?
Madden-Julian Oscillation (MJO) - How to interpret the index?
Is "remove commented out code" correct English?
How does a predictive coding aid in lossless compression?
What method can I use to design a dungeon difficult enough that the PCs can't make it through without killing them?
Why doesn't using multiple commands with a || or && conditional work?
Arrow those variables!
How to show a landlord what we have in savings?
Why was the shrinking from 8″ made only to 5.25″ and not smaller (4″ or less)?
How many equivalence relations on S have exactly 3 equivalence classes?
How many equivalence relations $S$ on $A$ are there for which $R⊆S$ ($R$ is an equivalence relation on a set $A$, with $4$ equivalence classes)How many equivalence-relations does the class have?Homeomorphism are equivalence relations, so what are the equivalence classes?Describe equivalence classes from equivalence relationsHow to prove equivalence relationsHow many ways of having 2 Equivalence Classes with Magnitude 3Stirling numbers and equivalence classesNumber of classes an equivalence relation partitions a set XEquivalence relations S on A with R being a relation on A with 4 equivalence classes.Uncountably Many Equivalence Classes
$begingroup$
Let S = 1,2,3,4,5,6,7,8. How many equivalence relations on S have exactly 3 equivalence classes?
The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like an unnecessary amount of calculations. Thanks in advance for any help!
combinatorics equivalence-relations stirling-numbers
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
$endgroup$
add a comment |
$begingroup$
Let S = 1,2,3,4,5,6,7,8. How many equivalence relations on S have exactly 3 equivalence classes?
The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like an unnecessary amount of calculations. Thanks in advance for any help!
combinatorics equivalence-relations stirling-numbers
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
$endgroup$
1
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54
add a comment |
$begingroup$
Let S = 1,2,3,4,5,6,7,8. How many equivalence relations on S have exactly 3 equivalence classes?
The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like an unnecessary amount of calculations. Thanks in advance for any help!
combinatorics equivalence-relations stirling-numbers
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
$endgroup$
Let S = 1,2,3,4,5,6,7,8. How many equivalence relations on S have exactly 3 equivalence classes?
The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like an unnecessary amount of calculations. Thanks in advance for any help!
combinatorics equivalence-relations stirling-numbers
combinatorics equivalence-relations stirling-numbers
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
edited Mar 21 at 4:53
Esther Rose
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
asked Mar 21 at 4:47
Esther RoseEsther Rose
655
655
1
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54
add a comment |
1
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54
1
1
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As I mentioned in the comments, we should count the number of surjective functions from $S$ to $1, 2, 3$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.
There are a total of $3^8$ possibly functions from $S$ to $1, 2, 3$. We need to subtract out the functions from $S$ to strict subsets $U$ of $1, 2, 3$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U subseteq 1, 2, 3$ with $|U| = 1$).
If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $1, 2, 3$.
Therefore, the total number of equivalence relations on $S$ with $3$ classes is
$$frac3^8 - 3 cdot (2^8 - 2) - 33! = 966.$$
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
$endgroup$
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
add a comment |
$begingroup$
To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.
So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= colorred966$.
Alternatively use the formula for these numbers
begineqnarray*
S(n,k) = frac1k! sum_i=0^k binomki i^n.
endeqnarray*
Which gives exactly the same as Theo.
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
$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%2f3156344%2fhow-many-equivalence-relations-on-s-have-exactly-3-equivalence-classes%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$
As I mentioned in the comments, we should count the number of surjective functions from $S$ to $1, 2, 3$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.
There are a total of $3^8$ possibly functions from $S$ to $1, 2, 3$. We need to subtract out the functions from $S$ to strict subsets $U$ of $1, 2, 3$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U subseteq 1, 2, 3$ with $|U| = 1$).
If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $1, 2, 3$.
Therefore, the total number of equivalence relations on $S$ with $3$ classes is
$$frac3^8 - 3 cdot (2^8 - 2) - 33! = 966.$$
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
$endgroup$
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
add a comment |
$begingroup$
As I mentioned in the comments, we should count the number of surjective functions from $S$ to $1, 2, 3$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.
There are a total of $3^8$ possibly functions from $S$ to $1, 2, 3$. We need to subtract out the functions from $S$ to strict subsets $U$ of $1, 2, 3$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U subseteq 1, 2, 3$ with $|U| = 1$).
If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $1, 2, 3$.
Therefore, the total number of equivalence relations on $S$ with $3$ classes is
$$frac3^8 - 3 cdot (2^8 - 2) - 33! = 966.$$
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
$endgroup$
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
add a comment |
$begingroup$
As I mentioned in the comments, we should count the number of surjective functions from $S$ to $1, 2, 3$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.
There are a total of $3^8$ possibly functions from $S$ to $1, 2, 3$. We need to subtract out the functions from $S$ to strict subsets $U$ of $1, 2, 3$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U subseteq 1, 2, 3$ with $|U| = 1$).
If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $1, 2, 3$.
Therefore, the total number of equivalence relations on $S$ with $3$ classes is
$$frac3^8 - 3 cdot (2^8 - 2) - 33! = 966.$$
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
$endgroup$
As I mentioned in the comments, we should count the number of surjective functions from $S$ to $1, 2, 3$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.
There are a total of $3^8$ possibly functions from $S$ to $1, 2, 3$. We need to subtract out the functions from $S$ to strict subsets $U$ of $1, 2, 3$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U subseteq 1, 2, 3$ with $|U| = 1$).
If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $1, 2, 3$.
Therefore, the total number of equivalence relations on $S$ with $3$ classes is
$$frac3^8 - 3 cdot (2^8 - 2) - 33! = 966.$$
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
edited Mar 21 at 22:33
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
answered Mar 21 at 5:18
Theo BenditTheo Bendit
20.1k12354
20.1k12354
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
add a comment |
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
$begingroup$
Thanks @Donald.
$endgroup$
– Theo Bendit
Mar 21 at 22:34
add a comment |
$begingroup$
To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.
So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= colorred966$.
Alternatively use the formula for these numbers
begineqnarray*
S(n,k) = frac1k! sum_i=0^k binomki i^n.
endeqnarray*
Which gives exactly the same as Theo.
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
$endgroup$
add a comment |
$begingroup$
To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.
So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= colorred966$.
Alternatively use the formula for these numbers
begineqnarray*
S(n,k) = frac1k! sum_i=0^k binomki i^n.
endeqnarray*
Which gives exactly the same as Theo.
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
$endgroup$
add a comment |
$begingroup$
To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.
So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= colorred966$.
Alternatively use the formula for these numbers
begineqnarray*
S(n,k) = frac1k! sum_i=0^k binomki i^n.
endeqnarray*
Which gives exactly the same as Theo.
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
$endgroup$
To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.
So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= colorred966$.
Alternatively use the formula for these numbers
begineqnarray*
S(n,k) = frac1k! sum_i=0^k binomki i^n.
endeqnarray*
Which gives exactly the same as Theo.
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
answered Mar 21 at 21:11
Donald SplutterwitDonald Splutterwit
23k21446
23k21446
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%2f3156344%2fhow-many-equivalence-relations-on-s-have-exactly-3-equivalence-classes%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
1
$begingroup$
How many functions from $S$ to $1, 2, 3$? How many of these functions are surjective (try counting the ones that aren't)? Don't forget to divide by $3!$ at the end.
$endgroup$
– Theo Bendit
Mar 21 at 4:54