Let X be a set with n elements, n &gt; 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)Θ(log⁡2n)Θ(n3)Θ(n2)Θ(n!)

Question

Let X be a set with n elements, n &amp;gt; 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)Θ(log⁡2n)Θ(n3)Θ(n2)Θ(n!)

Macsen Nixon · Accepted Answer

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&amp;gt;3). We are interested in the number of elements in the set A={f:X—&amp;gt;X∣f is a one-to-one correspondence} f:X→X 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⋅(n−1)⋅(n—2)⋅…⋅1=n! Thus there are n! one-to-one correspondences f:X≥X, which means that the set A contains n! elements. Finally we know that n! is θ (n!)

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!)

Answered question

Answer & Explanation

New Questions in Algebra I