Discrete Mathematics: 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?

    2. Example. $N=2, K=3$


    Example. $N=3, K=2$


    \[ \boxed{K^N} \]
  2. How many injective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    3. Example. $N=2, K=3$


    \[ \boxed{ \begin{cases} \dfrac{K!}{(K-N)!} & N \le K \\ 0 & N > K \end{cases} } \]
  3. How many surjective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    4. Example. $N=3, K=2$


    \[ \boxed{ \begin{cases} K!\,S(N,K) & N \ge K \\ 0 & N < K \end{cases} } \]
  4. How many bijective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements?

    5. Example. $N=3, K=3$


    \[ \boxed{ \begin{cases} N! & N = K \\ 0 & N \ne K \end{cases} } \]
  5. How many functions are there from a set with $N$ indistinguishable elements to a set with $K$ distinct elements?

    6. Example. $N=2, K=3$


    Example. $N=3, K=2$


    \[ \boxed{\binom{N+K-1}{K-1}} \]
  6. How many injective functions are there from a set with $N$ indistinguishable elements to a set with $K$ distinct elements?

    7. Example. $N=2, K=3$


    \[ \boxed{ \begin{cases} \binom{K}{N} & N \le K \\ 0 & N > K \end{cases} } \]
  7. How many surjective functions are there from a set with $N$ indistinguishable elements to a set with $K$ distinct elements?

    8. Example. $N=3, K=2$


    \[ \boxed{ \begin{cases} \binom{N-1}{K-1} & N \ge K \\ 0 & N < K \end{cases} } \]
  8. How many bijective functions are there from a set with $N$ indistinguishable elements to a set with $K$ distinct elements?


    9. Example. $N=3, K=3$


    \[ \boxed{ \begin{cases} 1 & N = K \\ 0 & N \ne K \end{cases} } \]
  9. How many functions are there from a set with $N$ distinct elements to a set with $K$ indistinguishable elements?

    10. Example. $N=3, K=2$


    Example. $N=2, K=3$


    Example. $N=3, K=3$


    \[ \boxed{ \begin{cases} B_N & K \ge N \\ \sum_{i=1}^{K} S(N,i) & K < N \end{cases} } \]
  10. How many injective functions are there from a set with $N$ distinct elements to a set with $K$ indistinguishable elements?

    11. Example. $N=2, K=3$


    \[ \boxed{ \begin{cases} 1 & N \le K \\ 0 & N > K \end{cases} } \]
  11. How many surjective functions are there from a set with $N$ distinct elements to a set with $K$ indistinguishable elements?

    12. Example. $N=3, K=2$


    \[ \boxed{ \begin{cases} S(N,K) & K \le N \\ 0 & K > N \end{cases} } \]
  12. How many bijective functions are there from a set with $N$ distinct elements to a set with $K$ indistinguishable elements?

    13. Example. $N=3, K=3$


    \[ \boxed{ \begin{cases} 1 & N = K \\ 0 & N \ne K \end{cases} } \]

Comments

Post a Comment

Popular posts from this blog

Discrete Mathematics: Permutations With Repetition

Image
Permutations With Repetition How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\)? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{N^L}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) without leading zero? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{(N-1)N^{L-1}}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears exactly \(K\) times? Example. $N=2, L=4, K=2$ Example. $N=3, L=3, K=1$ $$\boxed{\binom{L}{K}(N-1)^{L-K}}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears at least \(K\) times? Example. $N=2, L=4, K=2$ Example. $N=3,L=3, K=1$ $$ \boxed{ \sum_{t=K}^{L} \bi...
Read more