Intereting Posts

Find the value of k, (if any), for which the system below has unique, infinite or no solution.
intuition behind weak solution
Abstract Algebra
Logic question: Ant walking a cube
A non-noetherian ring with $\text{Spec}(R)$ noetherian
Can we construct a $\mathbb Q$-basis for the Pythagorean closure of $\mathbb Q?$
Some questions about functions of bounded variation: Jordan's theorem
How to get the minimum and maximum of one convex function?
Independent, Identically Distributed Random Variables
Cauchy Sequence in $X$ on $$ with norm $\int_{0}^{1} |x(t)|dt$
What's the General Expression For Probability of a Failed Gift Exchange Draw
Norm induced by convex, open, symmetric, bounded set in $\Bbb R^n$.
what is the sum of square of all elements in $U(n)$?
How many monotonically increasing sequences of natural numbers?
What is the difference between a complete orthonormal set and an orthonormal basis in a Hilbert space

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

- permutations of a multiset having symbols with fixed multiplicity
- A troublesome Counting Problem
- Combinatorics - pigeonhole principle question
- Formula for the number of connections needed to connect every node in a set?
- arrangement of $n$ oranges and $n$ apples around a circle
- Stirling Numbers and inverse matrices

Am I right? Thanks.

- A question on an unbounded function
- Summation of binomial coefficients
- Solve a recursion using generating functions?
- Dividing a square into equal-area rectangles
- Maximum of the Variance Function for Given Set of Bounded Numbers
- Sequence of continuous functions converges uniformly. Does it imply the limit function is continuous?
- Nonattacking rooks on a triangular chessboard
- What's the chance of an explicit series of integers in a limited random distribution?
- number of combination in which no two red balls are adjacent.
- Derivative of a function with respect to another function.

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

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.

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

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|} $“

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, |B| = n.

For one to one functions,

- if m < n, there are
**n!/(n-m)!**one to one functions from A to B. - if m = n, there are
**m!**one to one functions from A to B. - if m > n, there are
**0**one to one functions from A to B.

For onto fictions,

- if m < n, there are
**0**functions from A onto B. - if m = n, there are
**m!**onto functions. - if m = n+1, then there are
**(n)**functions A onto B.*( (n+1) C 2 )*(n-1)!

You can get more detailed information from this pdf document.

enter link description here

- Show that the following recurrence relation satisfies the inequality $\displaystyle f(1) + 2f(2) + \cdots + nf(n) \le \frac{n(n+1)(2n+1)}{6}$
- Chuck Norris' Coupling of Markov Chains: An Invariant Distribution
- prove that $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$
- Number of subgroups of $S_4$
- Give an example of a non compact Hausdorff space such that $\Delta$ is closed but $Y$ is not Hausdorff
- One sided Chebyshev's inequality
- Equivalent Definitions of Ideal Norm
- A universal property for the subspace topology
- Proving infintely many primes of the form 6k-1
- On Galois groups and $\int_{-\infty}^{\infty} \frac{x^2}{x^{10} – x^9 + 5x^8 – 2x^7 + 16x^6 – 7x^5 + 20x^4 + x^3 + 12x^2 – 3x + 1}\,dx$
- Prove that the set of integers bounded below is well-ordered.
- What is the best base to use?
- Solving an equation with floor function
- Limit points of $\cos n$.
- Show that $f(x)=g(x)$ for all $x \in \mathbb R$