Let X be a set with n elements, n > 3. Determine the size of the following set in terms of n, and give a big-Θ estimate for the answer. the set of all one-to-one correspondences X → X Θ(2n) Θ(log2 n) Θ(n3) Θ(n2) Θ(n!)

Rui Baldwin

Rui Baldwin

Answered question

2020-12-09

Let X be a set with n elements, n > 3. Determine the size of the following set in terms of n, and give a big-Θ estimate for the answer. the set of all one-to-one correspondences XXΘ(2n)Θ(log2n)Θ(n3)Θ(n2)Θ(n!)

Answer & Explanation

Macsen Nixon

Macsen Nixon

Skilled2020-12-10Added 117 answers

DEFINITIONS
The function f is onto if and only if for every clement  B there exist an clement a  A such that f(a)=b.
The function f is one-to-one if and only if f(a)=f(b) implies that a= b for all a and b in the domain.
f is a one-to-one correspondence and only if f is one-to-one and onto.
Fundamental counting principle: If the first event could occur in m ways and the second event could occur in n ways, then the number of ways that the two events could ocour in sequence is m*n
SOLUTION
X is a set with m elements (n>3).
We are interested in the number of elements in the set
A={f:X>Xf is a one-to-one correspondence}
f:XX can only be a one-to-one correspondence when every element in X has a unique image. This then implies that the first element in X has n possible images, the second element in X has n— 1 possible images, the third element in X has n — 2 possible images, etc.
First element: n ways
Second element: n — 1 ways
Third element: n — 2 ways
nth clement: 1 ways
By the fundamental counting principle:
n(n1)(n2)1=n! Thus there are n! one-to-one correspondences f:XX, which means that the set A contains n! elements. Finally we know that n! is θ (n!)

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?