Mixing
Number of surjective functions from a set with $m$ elements onto a set with $n$ elements
Clash Royale CLAN TAG#URR8PPP
up vote
12
down vote
favorite
I was trying to calculate the number of surjective (onto) functions from A to B.
Let a set $A$ contain $m$ elements and another set $B$ contain $n$ element i.e.
$$|A|=m, quad |B|=n.$$
Now, if $n>m$, no. of onto functions is $0$.
When $m ge n$,
since there should be no unrelated element in B, let us relate first n elements of a A to B,so that all elements of B gets related.
Hence total possibility for first n elements of A( which actually contain m elements ) is
$$n!$$
Now the remaining $m-n$ elements in $A$ can be related to any of the $n$ elements of $B$. Hence the total possibility of the remaining $m-n$ elements of $B$ is
$$n^m-n$$
Therefore total number of surjective function is$$n!*n^m-n$$
Is anything wrong in this calculation ?If its wrong ,can anyone suggest correct method with proof.
combinatorics functions permutations combinations
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
asked Jul 29 at 15:34
salvin
636
add a comment |Â
up vote
12
down vote
favorite
I was trying to calculate the number of surjective (onto) functions from A to B.
Let a set $A$ contain $m$ elements and another set $B$ contain $n$ element i.e.
$$|A|=m, quad |B|=n.$$
Now, if $n>m$, no. of onto functions is $0$.
When $m ge n$,
since there should be no unrelated element in B, let us relate first n elements of a A to B,so that all elements of B gets related.
Hence total possibility for first n elements of A( which actually contain m elements ) is
$$n!$$
Now the remaining $m-n$ elements in $A$ can be related to any of the $n$ elements of $B$. Hence the total possibility of the remaining $m-n$ elements of $B$ is
$$n^m-n$$
Therefore total number of surjective function is$$n!*n^m-n$$
Is anything wrong in this calculation ?If its wrong ,can anyone suggest correct method with proof.
combinatorics functions permutations combinations
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
asked Jul 29 at 15:34
salvin
636
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
More obviously related.
– Cameron Buie
Jul 29 at 16:15
add a comment |Â
up vote
12
down vote
favorite
up vote
12
down vote
favorite
I was trying to calculate the number of surjective (onto) functions from A to B.
Let a set $A$ contain $m$ elements and another set $B$ contain $n$ element i.e.
$$|A|=m, quad |B|=n.$$
Now, if $n>m$, no. of onto functions is $0$.
When $m ge n$,
since there should be no unrelated element in B, let us relate first n elements of a A to B,so that all elements of B gets related.
Hence total possibility for first n elements of A( which actually contain m elements ) is
$$n!$$
Now the remaining $m-n$ elements in $A$ can be related to any of the $n$ elements of $B$. Hence the total possibility of the remaining $m-n$ elements of $B$ is
$$n^m-n$$
Therefore total number of surjective function is$$n!*n^m-n$$
Is anything wrong in this calculation ?If its wrong ,can anyone suggest correct method with proof.
combinatorics functions permutations combinations
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
asked Jul 29 at 15:34
salvin
636
I was trying to calculate the number of surjective (onto) functions from A to B.
Let a set $A$ contain $m$ elements and another set $B$ contain $n$ element i.e.
$$|A|=m, quad |B|=n.$$
Now, if $n>m$, no. of onto functions is $0$.
When $m ge n$,
since there should be no unrelated element in B, let us relate first n elements of a A to B,so that all elements of B gets related.
Hence total possibility for first n elements of A( which actually contain m elements ) is
$$n!$$
Now the remaining $m-n$ elements in $A$ can be related to any of the $n$ elements of $B$. Hence the total possibility of the remaining $m-n$ elements of $B$ is
$$n^m-n$$
Therefore total number of surjective function is$$n!*n^m-n$$
Is anything wrong in this calculation ?If its wrong ,can anyone suggest correct method with proof.
combinatorics functions permutations combinations
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
asked Jul 29 at 15:34
salvin
636
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
edited Jul 29 at 22:30
Asaf Karagila
291k31402732
291k31402732
asked Jul 29 at 15:34
salvin
636
asked Jul 29 at 15:34
salvin
636
asked Jul 29 at 15:34
salvin
636
636
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
More obviously related.
– Cameron Buie
Jul 29 at 16:15
add a comment |Â
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
More obviously related.
– Cameron Buie
Jul 29 at 16:15
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
More obviously related.
– Cameron Buie
Jul 29 at 16:15
More obviously related.
– Cameron Buie
Jul 29 at 16:15
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
11
down vote
accepted
In general computing the number of surjections between finite sets is difficult.
Your procedure for obtaining the figure of $n! cdot n^m-n$ is overcounting, and also erroneous for another reason.
- It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
- It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $binommn$ ways of doing this, so your procedure should in fact yield $binommn cdot n! cdot n^m-n$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' subseteq A$ is a subset with $n$ elements, $f : A' to B$ is a bijection and $g : A setminus A' to B$ is an arbitrary function.
Even computing the number of surjections $A to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 cdot 2^m + 3$ of them (see here, for instance).
If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
add a comment |Â
up vote
8
down vote
You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $n choose 2(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $n choose 3(n-3)m$. The final expression is
$$n^m+sum_i=1^n-1(-1)^in choose i(n-i)^m$$
answered Jul 29 at 16:52
Ross Millikan
275k21185351
add a comment |Â
up vote
5
down vote
The number of surjections from a set of $m$ elements to a set of $n$ elements is
$$n! ;S(m,n)$$
where $S(m,n)$ is a Stirling number of the second kind.
answered Jul 29 at 21:07
awkward
5,06611021
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
11
down vote
accepted
In general computing the number of surjections between finite sets is difficult.
Your procedure for obtaining the figure of $n! cdot n^m-n$ is overcounting, and also erroneous for another reason.
- It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
- It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $binommn$ ways of doing this, so your procedure should in fact yield $binommn cdot n! cdot n^m-n$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' subseteq A$ is a subset with $n$ elements, $f : A' to B$ is a bijection and $g : A setminus A' to B$ is an arbitrary function.
Even computing the number of surjections $A to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 cdot 2^m + 3$ of them (see here, for instance).
If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
add a comment |Â
up vote
11
down vote
accepted
In general computing the number of surjections between finite sets is difficult.
Your procedure for obtaining the figure of $n! cdot n^m-n$ is overcounting, and also erroneous for another reason.
- It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
- It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $binommn$ ways of doing this, so your procedure should in fact yield $binommn cdot n! cdot n^m-n$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' subseteq A$ is a subset with $n$ elements, $f : A' to B$ is a bijection and $g : A setminus A' to B$ is an arbitrary function.
Even computing the number of surjections $A to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 cdot 2^m + 3$ of them (see here, for instance).
If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
add a comment |Â
up vote
11
down vote
accepted
up vote
11
down vote
accepted
In general computing the number of surjections between finite sets is difficult.
Your procedure for obtaining the figure of $n! cdot n^m-n$ is overcounting, and also erroneous for another reason.
- It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
- It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $binommn$ ways of doing this, so your procedure should in fact yield $binommn cdot n! cdot n^m-n$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' subseteq A$ is a subset with $n$ elements, $f : A' to B$ is a bijection and $g : A setminus A' to B$ is an arbitrary function.
Even computing the number of surjections $A to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 cdot 2^m + 3$ of them (see here, for instance).
If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
In general computing the number of surjections between finite sets is difficult.
Your procedure for obtaining the figure of $n! cdot n^m-n$ is overcounting, and also erroneous for another reason.
- It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
- It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $binommn$ ways of doing this, so your procedure should in fact yield $binommn cdot n! cdot n^m-n$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' subseteq A$ is a subset with $n$ elements, $f : A' to B$ is a bijection and $g : A setminus A' to B$ is an arbitrary function.
Even computing the number of surjections $A to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 cdot 2^m + 3$ of them (see here, for instance).
If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
answered Jul 29 at 15:46
Clive Newstead
47.8k471129
47.8k471129
add a comment |Â
add a comment |Â
up vote
8
down vote
You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $n choose 2(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $n choose 3(n-3)m$. The final expression is
$$n^m+sum_i=1^n-1(-1)^in choose i(n-i)^m$$
answered Jul 29 at 16:52
Ross Millikan
275k21185351
add a comment |Â
up vote
8
down vote
You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $n choose 2(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $n choose 3(n-3)m$. The final expression is
$$n^m+sum_i=1^n-1(-1)^in choose i(n-i)^m$$
answered Jul 29 at 16:52
Ross Millikan
275k21185351
add a comment |Â
up vote
8
down vote
up vote
8
down vote
You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $n choose 2(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $n choose 3(n-3)m$. The final expression is
$$n^m+sum_i=1^n-1(-1)^in choose i(n-i)^m$$
answered Jul 29 at 16:52
Ross Millikan
275k21185351
You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $n choose 2(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $n choose 3(n-3)m$. The final expression is
$$n^m+sum_i=1^n-1(-1)^in choose i(n-i)^m$$
answered Jul 29 at 16:52
Ross Millikan
275k21185351
answered Jul 29 at 16:52
Ross Millikan
275k21185351
answered Jul 29 at 16:52
Ross Millikan
275k21185351
answered Jul 29 at 16:52
Ross Millikan
275k21185351
275k21185351
add a comment |Â
add a comment |Â
up vote
5
down vote
The number of surjections from a set of $m$ elements to a set of $n$ elements is
$$n! ;S(m,n)$$
where $S(m,n)$ is a Stirling number of the second kind.
answered Jul 29 at 21:07
awkward
5,06611021
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
add a comment |Â
up vote
5
down vote
The number of surjections from a set of $m$ elements to a set of $n$ elements is
$$n! ;S(m,n)$$
where $S(m,n)$ is a Stirling number of the second kind.
answered Jul 29 at 21:07
awkward
5,06611021
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
add a comment |Â
up vote
5
down vote
up vote
5
down vote
The number of surjections from a set of $m$ elements to a set of $n$ elements is
$$n! ;S(m,n)$$
where $S(m,n)$ is a Stirling number of the second kind.
answered Jul 29 at 21:07
awkward
5,06611021
The number of surjections from a set of $m$ elements to a set of $n$ elements is
$$n! ;S(m,n)$$
where $S(m,n)$ is a Stirling number of the second kind.
answered Jul 29 at 21:07
awkward
5,06611021
edited Jul 29 at 21:19
answered Jul 29 at 21:07
awkward
5,06611021
answered Jul 29 at 21:07
awkward
5,06611021
answered Jul 29 at 21:07
awkward
5,06611021
5,06611021
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
add a comment |Â
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case?
– ml0105
Jul 29 at 21:08
4
4
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
@ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up).
– awkward
Jul 29 at 21:20
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%2f2866173%2fnumber-of-surjective-functions-from-a-set-with-m-elements-onto-a-set-with-n%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
Nitpick. If you are assuming A and B are both finite you should specifically state that.
– fleablood
Jul 29 at 15:49
It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path.
– hardmath
Jul 29 at 15:50
Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for.
– Cameron Buie
Jul 29 at 16:12
More obviously related.
– Cameron Buie
Jul 29 at 16:15