erEaNceNcE
New member
- Joined
- May 3, 2020
- Messages
- 1
Homework Statement:
Consider \(\displaystyle S_m = \{1, 2, 3, . . . , m\}\) and \(\displaystyle S_n = \{1, 2, 3, . . . , n\}\) with \(\displaystyle m, n \geq 3\).
(a) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\)?
(b) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) \in \{1, 2\}\) for at least one \(\displaystyle x \in S_m\)?
(c) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\) and \(\displaystyle f(y) \neq 2\) for any \(\displaystyle y \in S_m\)?
(d) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\) and \(\displaystyle f(y) = 2\) for at least one \(\displaystyle y \in S_m\)?
Attempt at a Solution:
I have tried to solve them. I would like to know if my answers are correct.
(a)
The total number of functions without any restrictions
\(\displaystyle =n^m\)
The number of functions such that \(\displaystyle f(x)\) is never \(\displaystyle 1\)
\(\displaystyle =(n-1)^m\)
The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\)
\(\displaystyle =n^m-(n-1)^m\)
(b)
The number of functions such that \(\displaystyle f(x) \notin \{1,2\}\)
\(\displaystyle =(n-2)^m\)
The number of functions such that \(\displaystyle f(x)\in \{1,2\}\) for at least one \(\displaystyle x\in S_m\)
\(\displaystyle =n^m-(n-2)^m\)
(c)
Total number of functions such that \(\displaystyle f(y)\neq 2\) for any \(\displaystyle y\in S_m\)
\(\displaystyle =(n-1)^m\)
Number of functions such that \(\displaystyle f(x)\) is never \(\displaystyle 1\) and and \(\displaystyle f(y)\) is never \(\displaystyle 2\)
\(\displaystyle =(n-2)^m\)
Number of functions that satisfy the requirements in this part
\(\displaystyle =(n-1)^m-(n-2)^m\)
(d)
Since the answer from part (b) includes:
-The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)\neq 2\) for any \(\displaystyle y\in S_m\); (which is just part(c))
-The number of functions such that \(\displaystyle f(x)=2\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)\neq 1\) for any \(\displaystyle y\in S_m\); (the number is equivalent to part(c)) and
-The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)=2\) for at least one \(\displaystyle y\in S_m\)
Answer for part (d) is just \(\displaystyle [\)part(b)\(\displaystyle -2\times\)part(c)\(\displaystyle ]\)
Hence,
the number of functions
\(\displaystyle =n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]\)
\(\displaystyle =n^m-2(n-1)^m+(n-2)^m\)
Consider \(\displaystyle S_m = \{1, 2, 3, . . . , m\}\) and \(\displaystyle S_n = \{1, 2, 3, . . . , n\}\) with \(\displaystyle m, n \geq 3\).
(a) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\)?
(b) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) \in \{1, 2\}\) for at least one \(\displaystyle x \in S_m\)?
(c) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\) and \(\displaystyle f(y) \neq 2\) for any \(\displaystyle y \in S_m\)?
(d) How many functions \(\displaystyle f\) are there from \(\displaystyle S_m\) to \(\displaystyle S_n\) such that \(\displaystyle f(x) = 1\) for at least one \(\displaystyle x \in S_m\) and \(\displaystyle f(y) = 2\) for at least one \(\displaystyle y \in S_m\)?
Attempt at a Solution:
I have tried to solve them. I would like to know if my answers are correct.
(a)
The total number of functions without any restrictions
\(\displaystyle =n^m\)
The number of functions such that \(\displaystyle f(x)\) is never \(\displaystyle 1\)
\(\displaystyle =(n-1)^m\)
The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\)
\(\displaystyle =n^m-(n-1)^m\)
(b)
The number of functions such that \(\displaystyle f(x) \notin \{1,2\}\)
\(\displaystyle =(n-2)^m\)
The number of functions such that \(\displaystyle f(x)\in \{1,2\}\) for at least one \(\displaystyle x\in S_m\)
\(\displaystyle =n^m-(n-2)^m\)
(c)
Total number of functions such that \(\displaystyle f(y)\neq 2\) for any \(\displaystyle y\in S_m\)
\(\displaystyle =(n-1)^m\)
Number of functions such that \(\displaystyle f(x)\) is never \(\displaystyle 1\) and and \(\displaystyle f(y)\) is never \(\displaystyle 2\)
\(\displaystyle =(n-2)^m\)
Number of functions that satisfy the requirements in this part
\(\displaystyle =(n-1)^m-(n-2)^m\)
(d)
Since the answer from part (b) includes:
-The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)\neq 2\) for any \(\displaystyle y\in S_m\); (which is just part(c))
-The number of functions such that \(\displaystyle f(x)=2\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)\neq 1\) for any \(\displaystyle y\in S_m\); (the number is equivalent to part(c)) and
-The number of functions such that \(\displaystyle f(x)=1\) for at least one \(\displaystyle x\in S_m\) and \(\displaystyle f(y)=2\) for at least one \(\displaystyle y\in S_m\)
Answer for part (d) is just \(\displaystyle [\)part(b)\(\displaystyle -2\times\)part(c)\(\displaystyle ]\)
Hence,
the number of functions
\(\displaystyle =n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]\)
\(\displaystyle =n^m-2(n-1)^m+(n-2)^m\)
