8
$\begingroup$

Suppose $X$ has $N$ elements and $Y$ has $M$ elements. How many one to one function are there from $X$ to $Y$? How many onto function are there from $X$ to $Y$?

The number of one to one functions is $N!$, because the max mapping to $Y$ is $N$.

The number of onto functions is $M^N - M + M((M-1)^N-(M-1))$, because the the range of the mapping has to cover all $M$ element

Am I right? Thanks.

Improve this question
$\endgroup$
  • $\begingroup$ Imagine arbitrarily writing down $N$ elements of $X$ into a column, now you can first choose out those $N$ function value you want to assign then permuting them from top to down: $$\binom{M}{N}\cdot N!$$. $\endgroup$ – linear_combinatori_probabi Sep 3 '20 at 19:11
9
$\begingroup$

Not quite.

For the one-to-one function, each element in $X$ is mapped to a unique element in $Y$. Therefore, there are $M$ ways to map the first element in $X$, and $M-1$ ways to map the second one, etc. There should be totally $M!/(M-N)!$ ways of one-to-one mapping when $M\geq N$. When $M<N$, you cannot get any one-to-one mapping.

For the onto function, there seems to be no simple, non-recusive formula for the number of onto functions.

See Stirling number

Improve this answer
$\endgroup$
3
$\begingroup$

Clearly if n < m there can be no onto functions from A to B, because under a function each element of A can map to only one element of B.

If n = m we have a bijection. The first element of A can map to any of the m elements of B. The second element of A can map to any of the remaining m - 1 elements of B, and so on. So the total number of onto functions is m!.

If n > m, there is no simple closed formula that describes the number of onto functions. We need to count the number of partitions of A into m blocks. For example, if n = 3 and m = 2, the partitions of elements a, b, and c of A into 2 blocks are: ab,c; ac,b; bc,a. Each of these partitions then describes a function from A to B. For example, the first partition -- ab,c -- says that a and b map to one element of B, and c maps to the other. Once we've counted the partitions we multiply by m!, just as in the bijection case, because for each partition the first block can map to any of the m elements of B, and so on.

The problem is that there is no simple, non-recursive way to calculate the number of partitions of an n-set into m blocks. These numbers are known as Stirling numbers of the second kind; see the reference below. See also sections 2.1.8 and 2.1.9 of the "Twelvefold Way" link.

So the best answer we can give for the case n ≥ m is: m! S(n,m), where S(n,m) is a Stirling number of the second kind.

Improve this answer
$\endgroup$
1
$\begingroup$

Just trying to give (possibly) better interpretation to make it more intuitive.

  • Definition of one-to-one from set A to set B: For every element in A, there is exactly one image in set B. In other words this is not one-to-one:
  • Thus:
    • one-to-one function is possible only when |A|<=|B|
    • "the range of A in codomain B will have exactly |A| elements. These elements can be mapped to elements in A in any order, i.e. they can be permutated in any possible way: $^{|B|}P_{|A|} $"
Improve this answer
$\endgroup$
1
$\begingroup$

I am not sure how can you get the answer of onto function because it is a complex question. However, I want to share what I know.

Given $|A| = m$ and $|B| = n$.

For one-to-one functions,

  1. if $m < n$, there are $\frac{n!}{(n-m)!}$ one-to-one functions from A to B.
  2. if $m = n$, there are $m!$ one-to-one functions from A to B.
  3. if m > n, there are $0$ one-to-one functions from A to B.

For onto functions,

  1. if $m < n$, there are $0$ functions from A onto B.
  2. if $m = n$, there are $m!$ onto functions.
  3. if $m = n+1$, then there are $n \cdot {n+1\choose 2} \cdot (n-1)! = \frac{n(n+1)!}{2!}$functions A onto B.

You can get more detailed information from this pdf document.

enter link description here

Improve this answer
$\endgroup$
0
$\begingroup$

Number of one to one functions is :

When we have a mapping from set $\Bbb A $to set $\Bbb B$ with m and n elements respectiely:

$^nC_m m! $

Or which can be elaborated as:

$^nP_m$

That is for each element in $\Bbb B$ We are selecting an element in $\Bbb A$ and then we arranging it so as to get a unique mapping.

This formula has inherent in itself that in case the mapping is such that n < m then there can be no one-to-one mapping at all.

I don't know about the number of onto functions and thus I have posted a question. Let us both wait for an answer to that question.

Number of onto functions

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.