Discrete Math Problems: VII The Twelvefold Way

The Twelvefold Way


  1. How many functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    By definition, a function assigns each of the \(N\) domain elements to exactly one of the \(K\) codomain elements. Thus, each domain element has \(K\) choices for its image, giving $ K^N $ total functions. This is a permutation with repetition, since we make \(N\) ordered choices from \(K\) possibilities, allowing repetition.


  2. How many injective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    By definition, an injective function assigns each of the \(N\) domain elements to a distinct element of the codomain. Thus, the first domain element has \(K\) choices, the second has \(K-1\) choices, the third has \(K-2\) choices, and so on. Therefore, the number of injective functions is $ K(K-1)(K-2)\cdots(K-N+1) = \frac{K!}{(K-N)!} $ provided that \(N \leq K\). This is a permutation without repetition, since we make \(N\) ordered choices from \(K\) possibilities without repeating elements. If \(N > K\), then there are no injective functions, since there are more domain elements than codomain elements, so at least two domain elements must map to the same codomain element.


  3. How many surjective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    By definition, a surjective function is a function in which every element of the codomain is the image of at least one element of the domain. The Stirling numbers of the second kind, $ \left\{ {N \atop K} \right\}, $ count the number of ways to partition a set of \(N\) distinct elements into \(K\) nonempty subsets:


    \(N \backslash K\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\)
    \(0\) \(1\) \(0\) \(0\) \(0\) \(0\) \(0\)
    \(1\) \(0\) \(1\) \(0\) \(0\) \(0\) \(0\)
    \(2\) \(0\) \(1\) \(1\) \(0\) \(0\) \(0\)
    \(3\) \(0\) \(1\) \(3\) \(1\) \(0\) \(0\)
    \(4\) \(0\) \(1\) \(7\) \(6\) \(1\) \(0\)
    \(5\) \(0\) \(1\) \(15\) \(25\) \(10\) \(1\)
    \(6\) \(0\) \(1\) \(31\) \(90\) \(65\) \(15\)

    Each subset is then assigned to a distinct codomain element in $ K! $ ways. Therefore, the number of surjective functions is $ K!\left\{ {N \atop K} \right\}. $


  4. How many bijective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    By definition, a bijective function is both injective and surjective. Thus, every element of the codomain is used exactly once. A bijection exists only when \(N=K\). If \(N=K\), then the first domain element has \(K\) choices, the second has \(K-1\) choices, the third has \(K-2\) choices, and so on. Therefore, the number of bijective functions is $ K! $ when \(N=K\). If \(N\ne K\), then there are no bijective functions.


  5. How many functions are there from a set with $N$ identical elements to a set with $K$ distinct elements?

    6. Since the \(N\) domain elements are identical, a function is determined only by how many elements map to each of the \(K\) distinct codomain elements. Thus, we must count the number of nonnegative integer solutions to $ x_1+x_2+\cdots+x_K=N $. This is a stars and bars problem: we arrange \(N\) stars and \(K-1\) bars. The stars represent the identical domain elements, and the bars divide them into \(K\) groups corresponding to the \(K\) codomain elements. Equivalently, this is a combination with repetition. Therefore, the total number of functions is $ \binom{N+K-1}{K-1}. $


  6. How many injective functions are there from a set with $N$ identical elements to a set with $K$ distinct elements?

    7. Since the domain elements are identical, the only thing that matters is which codomain elements are used. An injective function requires that no two domain elements map to the same codomain element, so we must select \(N\) distinct elements from the \(K\)-element codomain. Thus, the number of injective functions is $ \binom{K}{N} $ provided that \(N \leq K\). If \(N > K\), then there are no injective functions, since there are not enough distinct codomain elements to assign to each domain element.


  7. How many surjective functions are there from a set with \(N\) identical elements to a set with \(K\) distinct elements?

    8. A surjective function requires that every element of the codomain is used at least once. Since the domain elements are identical, a function is determined only by how many elements map to each codomain element. Let \(x_i\) denote the number of domain elements mapped to the \(i\)-th codomain element. Surjectivity requires $ x_1 + x_2 + \cdots + x_K = N, \quad x_i \geq 1. $ Define $ y_i = x_i - 1 \geq 0 $. Then $ y_1 + y_2 + \cdots + y_K = N-K. $ This is a stars and bars problem: we arrange \(N - K\) stars and \(K-1\) bars. Equivalently, this is a combination with repetition. The number of nonnegative integer solutions is given by $ \binom{N-1}{K-1} $ provided that \(N \geq K\). If \(N < K\), then no surjective function exists because there are not enough domain elements to map onto every codomain element.


  8. How many bijective functions are there from a set with $N$ identical elements to a set with $K$ distinct elements?

    A bijective function is both injective and surjective. Thus, every codomain element must receive exactly one domain element, which is only possible when $ N = K $. Since all domain elements are indistinguishable, every bijection looks the same. Therefore, if \(N = K\), then there exists exactly one bijective function. If \(N \ne K\), then there exists no bijective function.



  9. How many functions are there from a set with \(N\) distinct elements to a set with \(K\) identical elements?

    Since the codomain elements are identical, only the partition of the \(N\) distinct domain elements matters. A function is therefore determined by how the domain is divided into groups corresponding to the codomain elements that are used. If exactly \(i\) codomain elements are used, then the number of ways to partition the \(N\) distinct elements into \(i\) nonempty unlabeled groups is given by the Stirling number of the second kind $ \left\{ {N \atop i} \right\} $. Summing over all possible numbers of used codomain elements, where \(0 \le i \le K\), gives $ \sum_{i=0}^{K} \left\{ {N \atop i} \right\}. $ Therefore, the number of functions is $ \sum_{i=0}^{K} \left\{ {N \atop i} \right\} $. In particular, if \(K \geq N\), then $ \sum_{i=0}^{N} \left\{ {N \atop i} \right\} = B_N $ where \(B_N\) is the \(N\)-th Bell number, which counts the total number of partitions of a set with \(N\) elements:


    \(N\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\)
    \(B_N\) \(1\) \(1\) \(2\) \(5\) \(15\) \(52\) \(203\) \(877\) \(4140\)


  10. How many injective functions are there from a set with $N$ distinct elements to a set with $K$ identical elements?

    Since all \(K\) codomain elements are identical, there is effectively only one possible image value. An injective function requires that distinct domain elements map to distinct codomain elements. If \(N>1\), this is impossible because all domain elements would map to the same identical codomain element, violating injectivity. Therefore, there is exactly one injective function when \(N=0\) or \(N=1\), and there are no injective functions when \(N\ge2\).


  11. How many surjective functions are there from a set with $N$ distinct elements to a set with $K$ identical elements?

    Since the \(K\) codomain elements are identical, only the partition of the domain matters. A surjective function requires that every codomain element receive at least one domain element, so the \(N\) distinct domain elements must be partitioned into exactly \(K\) nonempty subsets. The number of such partitions is given by the Stirling number of the second kind: $ \left\{ {N \atop K} \right\} $.


  12. How many bijective functions are there from a set with $N$ distinct elements to a set with $K$ identical elements?

    A bijective function is both injective and surjective. Since the \(K\) codomain elements are identical, only the partition of the \(N\) distinct domain elements into \(K\) nonempty subsets matters. Surjectivity requires every codomain element to receive at least one domain element, giving $ \left\{ {N \atop K} \right\} $ possible partitions. For the function to also be injective, each subset must contain exactly one element, which is only possible when $ N = K $. In this case, $ \left\{ {N \atop N} \right\}=1, $ so there exists exactly one bijective function. If \(N \ne K\), then there exists no bijective function.

Comments

Post a Comment

Popular posts from this blog

Linear Algebra: I Scalars and Vectors

Scalars and Vectors A scalar is defined as a real number $c \in \mathbb{R}$ with 1 dimensional length $|c|$ and either positive or negative direction on the number line. A vector , denoted $\vec{v}$, is an ordered collection of scalars with dimension $n \geq 1$: Written as a column vector $$\vec{v} =\begin{bmatrix} v_1 \\ \vdots \\ v_n \end{bmatrix}\in \mathbb{R}^n $$ Written as row vector $$\vec{v}^\top =\begin{bmatrix} v_1 & \ldots & v_n \end{bmatrix}\in \mathbb{R}^n$$ Where $\top$ is the transpose operator that exchanges column vectors with row vectors. Note $(\vec{v}^\top)^\top = \vec{v}$. Also, scalars defined as real numbers always equal their own transpose $c^\top = c$. With magnitude $$\|\vec{v}\| = \|\vec{v}^\top\|=\sqrt{v_1^2+\ldots+v_n^2} \geq 0$$ And direction (with the exception of $\vec{0}$ where $\|\vec{0}\|=0$ and $\vec{0}$ has no direction). Row vectors can be treated as transposes of column vectors,...
Read more

Linear Algebra: XI Eigenvalues and Eigenvectors

Eigenvalues and Eigenvectors Let \( A \) be an \( n \) by \( n \) square matrix, defining a linear transformation \( T: \mathbb{R}^n \to \mathbb{R}^n \). A non-zero vector \( \vec{v} \) is called an eigenvector of matrix \( A \) / a linear transformation \( T \) if: $$ T(\vec{v}) = A\vec{v} = \lambda \vec{v} $$ for some scalar $\lambda$, called its eigenvalue , which can be either real or complex even if $A$ has all real values. A matrix \( A \) does not change its eigenvectors' directions since each \( A\vec{v} \) is a scalar multiple of \( \vec{v} \). An eigenvalue tells you the change in magnitude since \( \| \lambda \vec{v} \| = |\lambda| \|\vec{v}\| \), and its sign tells you its orientation. A square matrix $A$ has a zero eigenvalue if and only if $\mathrm{Null}(A)$ is non-trivial. If $\vec{v}$ is an eigenvector of $A$ with eigenvalue $\lambda$, then $c \vec{v}$ ($c \neq 0$) is also an eigenvector of $A$ with eigenvalue $\lambda$. The eig...
Read more

Linear Algebra: VIII The Fundamental Theorem of Linear Algebra

The Fundamental Theorem of Linear Algebra Consider a linear transformation $T: \mathbb{R}^n \rightarrow \mathbb{R}^m$ defined by $T(\vec{x}) = A\vec{x}$ where $A$ is an $m$ by $n$ matrix. The row echelon form and reduced row echelon form of a matrix described below are products of $m$ by $m$ elementary matrices (row operations) times $A$ / compositions of linear transformations described by these elementary matrices with $T$. Row Echelon Form (REF) An $m$ by $n$ matrix $A$ is in row echelon form , denoted $\text{REF}(A)$, if: Each row has a non-zero leading entry called its pivot . The next pivot is to the right of the previous pivot above it. Every entry below each pivot is zero. All zero rows are at the bottom. Leading variables of $A$ correspond to pivot columns in $\mathrm{REF}(A)$, and the corresponding columns of $A$ form a linearly independent set. Free variables of $A$ correspond to columns without a pivot in $\mathrm{REF}(A)...
Read more