- #1
HaRgIlIN
- 2
- 0
- Homework Statement
- Consider ##S_m = \{1, 2, 3, . . . , m\}## and ##S_n = \{1, 2, 3, . . . , n\}## with ##m, n \geq 3##.
(a) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m##?
(b) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) \in \{1, 2\}## for at least one ##x \in S_m##?
(c) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) \neq 2## for any ##y \in S_m##?
(d) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) = 2## for at least one ##y \in S_m##?
- Relevant Equations
- N/A
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
##=n^m##
The number of functions such that ##f(x)## is never ##1##
##=(n-1)^m##
The number of functions such that ##f(x)=1## for at least one ##x\in S_m##
##=n^m-(n-1)^m##
(b)
The number of functions such that ##f(x) \notin \{1,2\}##
##=(n-2)^m##
The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##
##=n^m-(n-2)^m##
(c)
Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##
##=(n-1)^m##
Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##
##=(n-2)^m##
Number of functions that satisfy the requirements in this part
##=(n-1)^m-(n-2)^m##
(d)
Since the answer from part (b) includes:
-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)\neq 2## for any ##y\in S_m##; (which is just part(c))
-The number of functions such that ##f(x)=2## for at least one ##x\in S_m## and ##f(y)\neq 1## for any ##y\in S_m##; (the number is equivalent to part(c)) and
-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)=2## for at least one ##y\in S_m##
Answer for part (d) is just ##[##part(b)##-2\times##part(c)##]##
Hence,
the number of functions
##=n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]##
##=n^m-2(n-1)^m+(n-2)^m##
(a)
The total number of functions without any restrictions
##=n^m##
The number of functions such that ##f(x)## is never ##1##
##=(n-1)^m##
The number of functions such that ##f(x)=1## for at least one ##x\in S_m##
##=n^m-(n-1)^m##
(b)
The number of functions such that ##f(x) \notin \{1,2\}##
##=(n-2)^m##
The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##
##=n^m-(n-2)^m##
(c)
Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##
##=(n-1)^m##
Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##
##=(n-2)^m##
Number of functions that satisfy the requirements in this part
##=(n-1)^m-(n-2)^m##
(d)
Since the answer from part (b) includes:
-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)\neq 2## for any ##y\in S_m##; (which is just part(c))
-The number of functions such that ##f(x)=2## for at least one ##x\in S_m## and ##f(y)\neq 1## for any ##y\in S_m##; (the number is equivalent to part(c)) and
-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)=2## for at least one ##y\in S_m##
Answer for part (d) is just ##[##part(b)##-2\times##part(c)##]##
Hence,
the number of functions
##=n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]##
##=n^m-2(n-1)^m+(n-2)^m##